這期內(nèi)容當(dāng)中小編將會給大家?guī)碛嘘P(guān)使用LeetCode怎么求最長回文子串，文章內(nèi)容豐富且以專業(yè)的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

目前創(chuàng)新互聯(lián)已為近1000家的企業(yè)提供了網(wǎng)站建設(shè)、域名、網(wǎng)站空間、網(wǎng)站運(yùn)營、企業(yè)網(wǎng)站設(shè)計(jì)、建湖網(wǎng)站維護(hù)等服務(wù)，公司將堅(jiān)持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長，共同發(fā)展。

描述

難度：中等

給你一個(gè)字符串 s，找到 s 中最長的回文子串。

示例 1：

輸入：s = "babad"
輸出："bab"
解釋："aba" 同樣是符合題意的答案。

示例 2：

輸入：s = "cbbd"
輸出："bb"

示例 3：

輸入：s = "a"
輸出："a"

示例 4：

輸入：s = "ac"
輸出："a"

提示：

1 <= s.length <= 1000 s 僅由數(shù)字和英文字母（大寫和/或小寫）組成

Solution

中心擴(kuò)散法

解題思路

• 都是回文數(shù)，這次是最長的回文數(shù)，并且包含字符串和數(shù)字，所以跟之前第五題的回文數(shù)，完全是兩個(gè)題，沒有可借鑒的地方

• 最終的結(jié)果是需要在字符串中找到最長的回文數(shù)，那么我們可以假定從字符串的每個(gè)字符開始，都有回文數(shù)，通過遍歷整體字符串的長度，并且算出每個(gè)字符回文數(shù)的長度，最后比較最長的數(shù)即可

• 假定每個(gè)字符都是存在回文數(shù)的，那么只有兩種情況，

• 回文子串長度為奇數(shù)（如aba，中心是(b)）

• 回文子串長度為偶數(shù)（如abba，中心是(b,b)

• 無論字符串S是奇數(shù)還是偶數(shù)，判斷回文數(shù)從當(dāng)前字符開始，M==N，其中M為中心的開始，N為相鄰的數(shù)字，奇數(shù)時(shí)，MN為同一個(gè)字符，偶數(shù)時(shí)，MN為M,N=(M+1)，如果S[M]==S[N]，則進(jìn)行擴(kuò)散，使M--,N++，繼續(xù)判斷S[M--],S[N++]的值，相等則繼續(xù)M--,N++，直到S[M--],S[N++]不相等或者超越邊界(M<0 OR N > = S.length())為止

CODE

class Solution {
    public String longestPalindrome(String s) {
         int len = s.length();
         String res = "";
      	 //如果小于2，直接返回
         if(len < 2){
             return s;
         }
         for(int i =0;i<len ; i++){
           	//奇數(shù)情況，兩個(gè)均為i
            res = sub(s,i,i,res)
            //偶數(shù)情況，中心數(shù)為i,i+1
            res = sub(s,i,i+1,res);
         }
         return res;
    }

    public String sub(String s,int m,int n,String res){
      	//m,n在范圍內(nèi)，并且s[m] == s[n]
        while(m>=0 && (n < s.length()) && (s.charAt(m) == s.charAt(n))){
          	//擴(kuò)散，對應(yīng)--
            m--;
          	//擴(kuò)散,對應(yīng)++
            n++;
        }
      	//這里其實(shí)是(n-1)-(m+1)-1,在上面while之后，會m--以及n++,比實(shí)際位置偏差一位
        if((n-m-1) > res.length()){
          	//截取m+1位置，到n-1的地方，上面while比實(shí)際位置偏差一位，所以m需要+1，n不需要-1
            res=s.substring(m+1,n);
        }
        return res;
    }
}

復(fù)雜度

• 時(shí)間復(fù)雜度：O(N2)，N為字符串長度，每個(gè)字符串向外遍歷最多可能N個(gè)

• 空間復(fù)雜度：O(1)

結(jié)果

• 執(zhí)行用時(shí)：37 ms, 在所有 Java 提交中擊敗了76.50%的用戶

• 內(nèi)存消耗：39 MB, 在所有 Java 提交中擊敗了58.36%的用戶

上述就是小編為大家分享的使用LeetCode怎么求最長回文子串了，如果剛好有類似的疑惑，不妨參照上述分析進(jìn)行理解。如果想知道更多相關(guān)知識，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。

分享名稱：使用LeetCode怎么求最長回文子串
分享URL：http://www.chinadenli.net/article40/ggiieo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站制作、建站公司、外貿(mào)建站、網(wǎng)站收錄、網(wǎng)站維護(hù)、微信公眾號

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)