問(wèn)題

求最長(zhǎng)回文子串

思路

如果考慮O(n)的動(dòng)態(tài)規(guī)劃，比如用f(i)來(lái)代表以當(dāng)前位置為結(jié)尾的回文子串的最大長(zhǎng)度，會(huì)遇到一個(gè)問(wèn)題，就是說(shuō)f(i)不僅僅取決于f(i-1)，有可能取決于i-1位置上回文子串的次最大長(zhǎng)度等等。比如這個(gè)字符串 bananas，下標(biāo)i從0開(kāi)始的話，f(3)=3，但是因?yàn)閒(3)是在1("a")和3("ana")中取的最大長(zhǎng)度，舍棄了1("a")，所以只是通過(guò)f(3)=3來(lái)判斷的話，會(huì)發(fā)現(xiàn)f(4)無(wú)法延續(xù)這一回文串，從而得出f(4)=1的錯(cuò)誤結(jié)果。其實(shí)f(4)延長(zhǎng)了f(3)的次長(zhǎng)回文子串，故f(4)=1+2=3

• 思路1：
  那么先不考慮O(n)的動(dòng)態(tài)規(guī)劃，我們考慮O(n^2)的動(dòng)態(tài)規(guī)劃，自頂向下分析，f(i,j)表示s(i,j)子串是否是回文，那么顯然有
  f(i,j) = true (i>=j)
  f(i,j) = true (f(i+1,j-1) and s(i)==s(j))
  此時(shí)自底向上遍歷即可

• 思路2
  再考慮記憶化搜索，f(i,j)定義為s(i,j)內(nèi)最大回文子串長(zhǎng)度，有遞推式
  f(i,j)就是當(dāng)前位置的子串長(zhǎng)度
  f(i,j) = j-i+1 if (i >= j-1 and s(i)==s(j))
  f(i,j) = j-i+1 if (s(i)==s(j) &&f(i+1,j-1)==s(i+1,j-1))
  記憶化搜索
  f(i,j) = max(f(i+1)(j-1),f(i)(j-1),f(i+1)(j))
  這里注意兩點(diǎn)，首先如果把f(i,j)直接定義成子串，思路和時(shí)間復(fù)雜度都是正確的，但是會(huì)TLE。。。其次只有f(i,j)是當(dāng)前位置子串時(shí)才會(huì)更新結(jié)果，所以其實(shí)最長(zhǎng)回文子串長(zhǎng)度的代碼和最長(zhǎng)回文子串的代碼只相差幾行~

代碼

• dp

    public String longestPalindrome(String s) {
        if(s==null || s.length()==0) return "";
        int dp[][] = new int[s.length()][s.length()];

        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j+i < s.length(); j++) {
                dp[j][j+i] = dp[j][j+i]!=0?dp[j][j+i]:(isPalindrome(s,j,j+i,dp)?2:1);
            }
        }

        int max = 0;
        String res = "";

        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                if(dp[i][j]==2 && j-i+1>max){
                    max = j-i;
                    res = s.substring(i,j+1);
                }
            }
        }

        return res;
    }

    public boolean isPalindrome(String s, int start, int end, int dp[][]){
        if (dp[start][end]>0) return dp[start][end]==2;
        if(end-start<=1) return s.charAt(start)==s.charAt(end);
        return isPalindrome(s,start+1,end-1,dp) && s.charAt(start)==s.charAt(end);
    }

• 記憶化搜索

    public String longestPalindrome(String s){
        if(s==null || s.length()==0) return "";

        int dp[][] = new int[s.length()][s.length()];
        String res="";
        int max = 0;

        for (int i = s.length()-1; i>=0;i--) {
            for (int j = i; j < s.length(); j++) {
                if(s.charAt(i)==s.charAt(j)){
                    if(j-i>1 && dp[i+1][j-1]==j-i-1) {
                        dp[i][j] = 2 + dp[i + 1][j - 1];
                        if(dp[i][j]>max){max=dp[i][j];res = s.substring(i,j+1);}
                    }
                    else if(j-i<=1){
                        dp[i][j] = j-i+1;
                        if(dp[i][j]>max){max=dp[i][j];res = s.substring(i,j+1);}
                    }
                }

                if(j>0 && i<s.length()-1)
                    dp[i][j] = max(dp[i][j],dp[i][j-1],dp[i+1][j],dp[i+1][j-1]);
            }
        }

        return res;
    }

Ref

https://leetcode.com/problems/longest-palindromic-substring/
https://tarokuriyama.com/projects/palindrome2.php