题目描述

求字符串的最长回文子串。

动归解法

之前写了两题动归的题，想练习一下动态规划，现在时间是 2017-03-27 02:18:52 ，走了很多弯路，折腾了一个小时，终于独立搞出了状态转移方程，目前dp对我来说还是挺艰难的…

定义s[i,j]标志着以i开头j结尾的子串是否是回文子串
s[i,j] (i <= j) = 1 if i == j
                = 1 if i == j-1 && a[i] == a[j]
                = 0 if i == j-1 && a[i] != a[j]
                = 0 if s[i+1, j-1] == 0
                = 0 if s[i+1, j-1] == 1 && a[i] != a[j]
                = 1 if s[i+1, j-1] == 1 && a[i] == a[j]

化简 =>

s[i,j] (i <= j) = 1            if i == j
                = a[i] == a[j] if i == j-1
                = s[i+1, j-1] && (a[i] == a[j])

代码

string longestPalindrome(string s) {
    int dp[1000][1000];
    memset(dp, -1, 1000000 * sizeof(int));
    int maxLen = 1, maxi = 0;
    for (int i = s.length() - 1; i >= 0; i--) {
        for (int j = s.length() - 1; j >= i; j--) {
            if (i == j) {
                dp[i][j] = 1;
            } else if (i == j - 1) {
                if (dp[i][j] = (s[i] == s[j])) {
                    if (j - i + 1 > maxLen) {
                        maxi = i;
                        maxLen = j - i + 1;
                    }
                }
            } else if (dp[i][j] = dp[i + 1][j - 1] && (s[i] == s[j])) {
                if (j - i + 1 > maxLen) {
                    maxi = i;
                    maxLen = j - i + 1;
                }
            }
        }
    }
    return s.substr(maxi, maxLen);
}

再提供一个其它解法的代码(来源)

public class Solution {
    private int lo, maxLen;

    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2)
            return s;

        for (int i = 0; i < len - 1; i++) {
            extendPalindrome(s, i, i); //assume odd length, try to extend Palindrome as possible
            extendPalindrome(s, i, i + 1); //assume even length.
        }
        return s.substring(lo, lo + maxLen);
    }

    private void extendPalindrome(String s, int j, int k) {
        while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
            j--;
            k++;
        }
        if (maxLen < k - j - 1) {
            lo = j + 1;
            maxLen = k - j - 1;
        }
    }
}