Leetcode 5 Longest Palindromic Substring (最长回文子字符串）(动态规划)

Leetcode 5

题目描述

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"

方法一

  方法一关键思想，每当我们向右移动时，我们只需要考虑使用这个新字符作为尾巴是否可以产生新的回文字符串，其长度为（当前长度+1）或（当前长度+2）。 方法一优于方法二采用的动态规划。
  Java我们提供两种方法，由运行时间，我们可以看出使用char[]性能比substring()和charAt()更优。

** Solution One -- Method One **
** 6ms, 40.8MB **
class Solution {
    public String longestPalindrome(String s) {
        if (s.length() < 1) return s;
        int curLen = 0;
        String res = "";
        char[] chr = s.toCharArray();
        for (int i = 0; i < s.length(); ++i) {
            if (isPalindrome(chr, i - curLen - 1, i)) {
                res = s.substring(i - curLen - 1, i + 1);
                curLen += 2;
            } else if (isPalindrome(chr, i - curLen, i)) {
                res = s.substring(i - curLen, i + 1);
                curLen += 1;
            }
        }
        return res;
    }
    private boolean isPalindrome(char[] chr, int i, int j){
        if (i < 0 ) return false;
        while (i < j) 
            if (chr[i++] != chr[j--])
                return false;
        return true;
    }
}

** Solution One -- Method Two **
** 14ms, 41.3MB **
class Solution {
    public String longestPalindrome(String s) {
        String res = "";
        int currLength = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (isPalindrome (s , i - currLength - 1, i)) {
                res = s.substring(i - currLength - 1,i + 1);
                currLength = currLength + 2;
            } else if (isPalindrome(s, i - currLength, i)) {
                res = s.substring(i - currLength, i + 1);
                currLength = currLength + 1;
            }
        }
        return res;
    }
    public boolean isPalindrome(String s, int begin, int end){
        if(begin<0) return false;
        while(begin < end)
        	if(s.charAt(begin++) != s.charAt(end--)) return false;
        return true;
    }
}

** Solution One **
** Python **
** 364ms, 11.8MB **
class Solution(object):
    def longestPalindrome(self, s):
        if (len(s) <= 1) : 
            return s
        curLen = 0
        res = ""
        for i in range(len(s)) :
            if (self.isPalindrome(s, i - curLen - 1, i)) :
                res = s[i - curLen - 1 : i + 1]
                curLen += 2
            elif (self.isPalindrome(s, i - curLen, i)) :
                res = s[i - curLen : i + 1]
                curLen += 1
        return res
    def isPalindrome(self, s, i, j):
        if (i < 0) :
            return False
        while (i < j) :
            if (s[i] != s[j]) :
                return False
            i += 1
            j -= 1
        return True

方法二 ： 动态规划

  方法二采用动态规划，dp[j][i]表示s[j:i+1]是回文子串与否。

** Solution Two **
** 55ms,  43.4MB **
public class Solution {
    public String longestPalindrome(String s) {
        if(s == null || s.length() == 0) {
            return "";
        }
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        int start = 0;
        int end = 0;
        int max = 0;
        char[] chr = s.toCharArray();
        for (int i = 0; i < s.length(); ++i) {
            for (int j = 0; j <= i; ++j) {
                if (chr[i] == chr[j] && (i - j <= 2 || dp[j+1][i-1])) {
                    dp[j][i] = true;
                }
                if (dp[j][i] && max < i - j + 1) {
                    max = i - j + 1;
                    start = j;
                    end = i;
                }
            }
        }
        return s.substring(start, end + 1);
    }
}