最长回文子串

骑猪看日落 2021-09-21 05:28 404阅读 0赞

**【题目】**

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

输入: “babad”  
输出: “bab”  
注意: “aba” 也是一个有效答案。

### 解法一、暴力法 ###

很明显，暴力法将选出所有子字符串可能的开始和结束位置，并检验它是不是回文。

*  时间复杂度：O(n^3)
 *  空间复杂度：O(1)

**【代码】**

public String longestPalindrome1(String s) { 
            if (s==null || s.length()==0) return "";
            int i,j,l,left,right,temp,resLeft,resRight;
            l = 1;
            resLeft = resRight =0;
            for (i=0; i<s.length();i++) { 
                for (j=i+1;j<s.length();j++) { 
                    left = i;
                    right = j;
                    while (left<right) { 
                        if (s.charAt(left) == s.charAt(right)) { 
                            left ++;
                            right --;
                        } else { 
                            break;
                        }
                    }
                    if (left < right) { 
                        temp = 0;
                    } else { 
                        temp = j - i + 1;
                    }
    
                    if (l < temp) { 
                        l = temp;
                        resLeft = i;
                        resRight = j;
                    }
                }
            }
    
            return s.substring(resLeft,resRight+1);
        }

### 解法二、动态规划 ###

/\*\*  
\* 动态规划进阶：二维数组和公式  
\* dp\[i\]\[j\] 表示 i到j是回文子串  
\* dp\[i+1\]\[j+1\]是回文子串的条件：dp\[i\]\[j\]是回文并且s(i+1)==s(j+1)  
\* dp\[i\]\[i+1\]是回文，只需要，s(i)==s(i+1)  
\* 边界：所有的单字符以及二回文子串  
\* dp\[i\]\[i\] 全部是回文子串  
\* 判断dp\[i\]\[i+1\]是不是回文，条件：s(i)==s(i+1)  
\* \*/

这产生了一个直观的动态规划解法，我们首先初始化一字母和二字母的回文，然后找到所有三字母回文，并依此类推…

*  时间复杂度：O(n^2)
 *  空间复杂度：O(n^2)

**【代码】**

public String longestPalindrome(String s) { 
            if (s==null || s.length()==0) return "";
    
            int i,j,len,l,r,res,k;
            len = s.length();
            boolean[][] dp = new boolean[len][len];
    
            // 初始化边界，把回文子串长度1和2的找出来
            dp[0][0] = true;
            l = r = 0;
            res = 1;
            for (i=1; i<len; i++) { 
                dp[i][i] = true;
                if (s.charAt(i-1) == s.charAt(i)) { 
                    dp[i-1][i] = true;
                    res = 2;
                    l = i-1;
                    r = i;
                }
            }
    		
    		//i表示检索的子串长度，等于3表示先检索长度为3的子串
            for (i=3; i<=len; i++) { 
                for (j=0; (j+i-1)<len; j++) { 
                    k = j+i-1;
                    if (dp[j+1][k-1] && s.charAt(j)==s.charAt(k)) { 
                        dp[j][k] = true;
                        if (res < (k-j+1)) { 
                            res = k-j+1;
                            l = j;
                            r = k;
                        }
                    }
    
                }
            }
            return s.substring(l,r+1);
        }

这里有几个需要注意的地方：

*  动态规划从来都是当前阶段i,j 根据之前的状态（无论是前一状态还是前几个状态）的条件符合情况来判断是否成立，而不是根据当前状态去判断后面的状态；
 *  简而言之：**dp\[i\]\[j\] = \{dp\[i-index\]\[j-index\]\}**,而不是dp\[i+index\]\[j+index\] = \{dp\[x\]\[y\]\},这是因为处理当前的dp可以很好的控制边界，保证边界不越界
 *  第二个需要注意的地方是，动态规划，阶段性不仅仅限制于一层的变化，需要考虑多层次的状态转移。