5. Longest Palindromic Substring (dp)

[Shawngbk]

动态规划，思路比较复杂一些，但是实现代码会比较简短。基本思路是外层循环i从后往前扫，内层循环j从i当前字符扫到结尾处。过程中使用的历史信息是从i+1到n之间的任意子串是否是回文已经被记录下来，所以不用重新判断，只需要比较一下头尾字符即可。这种方法使用两层循环，时间复杂度是O(n^2)。而空间上因为需要记录任意子串是否为回文，需要O(n^2)的空间，代码如下：

[java] view plain copy 在CODE上查看代码片派生到我的代码片 public String longestPalindrome(String s) {
if(s == null || s.length()==0)
return "";
boolean[][] palin = new boolean[s.length()][s.length()];
String res = "";
int maxLen = 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) && (j-i<=2 || palin[i+1][j-1]))
{
palin[i][j] = true;
if(maxLen<j-i+1)
{
maxLen=j-i+1;
res = s.substring(i,j+1);
}
}
}
}
return res;
}

方法2: Time O(n^2), Space O(1)

public String longestPalindrome(String s) { if (s.isEmpty()) { return null; }

if (s.length() == 1) {
    return s;
}

String longest = s.substring(0, 1);
for (int i = 0; i < s.length(); i++) {
    // get longest palindrome with center of i
    String tmp = helper(s, i, i);
    if (tmp.length() > longest.length()) {
        longest = tmp;
    }

    // get longest palindrome with center of i, i+1
    tmp = helper(s, i, i + 1);
    if (tmp.length() > longest.length()) {
        longest = tmp;
    }
}

return longest;

}

// Given a center, either one letter or two letter, // Find longest palindrome public String helper(String s, int begin, int end) { while (begin >= 0 && end <= s.length() - 1 && s.charAt(begin) == s.charAt(end)) { begin--; end++; } return s.substring(begin + 1, end); }

[Shawngbk]

考