題目

最長(zhǎng)回文子串

https://leetcode-cn.com/problems/longest-palindromic-substring/

公眾號(hào) 《java編程手記》記錄JAVA學(xué)習(xí)日常，分享學(xué)習(xí)路上點(diǎn)點(diǎn)滴滴，從入門到放棄，歡迎關(guān)注

描述

難度：中等

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

示例 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ù)，這次是最長(zhǎng)的回文數(shù)，并且包含字符串和數(shù)字，所以跟之前第五題的回文數(shù)，完全是兩個(gè)題，沒有可借鑒的地方
• 最終的結(jié)果是需要在字符串中找到最長(zhǎng)的回文數(shù)，那么我們可以假定從字符串的每個(gè)字符開始，都有回文數(shù)，通過(guò)遍歷整體字符串的長(zhǎng)度，并且算出每個(gè)字符回文數(shù)的長(zhǎng)度，最后比較最長(zhǎng)的數(shù)即可
• 假定每個(gè)字符都是存在回文數(shù)的，那么只有兩種情況，
  • 回文子串長(zhǎng)度為奇數(shù)（如aba，中心是(b)）
  • 回文子串長(zhǎng)度為偶數(shù)（如abba，中心是(b,b)
• 無(wú)論字符串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())為止

image-20210418001408582

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ò)散，對(duì)應(yīng)--
            m--;
            //擴(kuò)散,對(duì)應(yīng)++
            n++;
        }
        //這里其實(shí)是(n-1)-(m+1)-1,在上面while之后，會(huì)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為字符串長(zhǎng)度，每個(gè)字符串向外遍歷最多可能N個(gè)

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

結(jié)果

• 執(zhí)行用時(shí)：37 ms, 在所有 Java 提交中擊敗了76.50%的用戶
• 內(nèi)存消耗：39 MB, 在所有 Java 提交中擊敗了58.36%的用戶

動(dòng)態(tài)規(guī)劃

第一次接觸動(dòng)態(tài)規(guī)劃，很遺憾，看了半天的動(dòng)態(tài)規(guī)劃還是沒能看明白，后續(xù)看明白補(bǔ)充進(jìn)來(lái)

我曾在銀色平原漫步,也曾在青草之河垂釣，這片土地認(rèn)識(shí)我，我們?nèi)舨粓?jiān)強(qiáng)，就將滅亡