【leetcode5】 5. Longest Palindrom

• 关键字：动态规划、回文字符串
• 难度：Medium
• 题目大意：输出一个字符串的最长回文子串

题目：

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:

Input: "cbbd"
Output: "bb"

解题思路：

• 思路一：
  以每一个字符为中心，往两边扩散来找，需要考虑字符串长度为奇 数和偶数的情形；
• 思路二：动态规划，以p(i,j)表示从字符串下标i到下标j字符是否为回文串，则可分情况讨论：
  • i==j时：
    p(i, j) = true
  • j-i=1时：
    p(i, j)=s.charAt(i)==s.charAt(j) j-i=1;
  • j-i>1时：
    p(i, j)=s.charAt(i)==s.charAt(j)&&( j-i<2||p(i+1,j-1));

填充dp数组时，注意逆序填充，可结合下图例子理解：

解法1：

class Solution {
        public String longestPalindrome(String s) {
        if(s==null||s.length()==0) return s;
        int len = s.length();
        int maxLen = 1;
        int start = 0;
        for(int i=0;i<len;i++) {
            //需要考虑字符串长度为奇数偶数的问题
            int cur = Math.max(process(s,i,i,maxLen),process(s,i,i+1,maxLen)); 
            if(cur>maxLen) {
                maxLen = cur;
                start = i-(maxLen-1)/2;
            }
        }

        return s.substring(start,start+maxLen);
    }
    private int process(String s, int l, int r,int maxLen){
        while(l>=0&&r<s.length()) {
            if(s.charAt(l)==s.charAt(r)) {
                if(maxLen<r-l+1) {
                    maxLen = r-l+1;
                }
                l--;
                r++;
            }
            else{
                   break; 
                }
        }
        return maxLen;
    }
}

解法2：

class Solution {
    public static String longestPalindrome(String s) {
        if(s==null||s.length()==0) return s;
        int len = s.length();
        boolean [][] dp = new boolean[len+1][len+1];
        int maxLen = 1;
        int start = 0;
        //初始化i==j时dp数组的值为true
        for(int i=1;i<len+1;i++) {
            for(int j=1;j<len+1;j++) {
                if(j==i) dp[i][j] = true;
            }
        }
        //根据上述递推式，可知dp二维数组需要逆序填充
        for(int i=len;i>0;i--) {
            for(int j=len;j>i;j--) {
                if(s.charAt(i-1)==s.charAt(j-1)&&(dp[i+1][j-1]||j-i<2)) {
                    dp[i][j] = true;
                    if(maxLen<j-i+1) {
                        maxLen = j-i+1;
                        start = i-1;
                    }
                }

            }
        }
        return s.substring(start,start+maxLen);
    }

}