LeetCode 5. Longest Palindromic Substring

[Woodyiiiiiii]

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"

---

这道题要求我们找到一个字符串中最长的回文字符串。LeetCode 中关于回文串的题共有五道，除了这道，其他的LeetCode四道为9. Palindrome Number，125. Valid Palindrome，131. Palindrome Partitioning，132. Palindrome Partitioning II。

传统的验证回文串的方法就是两个两个的对称验证是否相等，
那么对于找回文字串的问题，就要以每一个字符为中心，
像两边扩散来寻找回文串，这个算法的时间复杂度是 O(n*n)，
而且要注意奇偶情况，由于回文串的长度可奇可偶，
比如 "bob" 是奇数形式的回文，"noon" 就是偶数形式的回文，
两种形式的回文都要搜索，对于奇数形式的，我们就从遍历到的位置为中心，
向两边进行扩散，对于偶数情况，
我们就把当前位置和下一个位置当作偶数行回文的最中间两个字符，然后向两边进行搜索。
C++解法如下：
class Solution {
public:
    string longestPalindrome(string s) {
        if (s.size() < 2) return s;
        int n = s.size(), maxLen = 0, start = 0;
        for (int i = 0; i < n - 1; ++i) {
            searchPalindrome(s, i, i, start, maxLen);
            searchPalindrome(s, i, i + 1, start, maxLen);
        }
        return s.substr(start, maxLen);
    }
    void searchPalindrome(string s, int left, int right, int& start, int& maxLen) {
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            --left; ++right;
        }
        if (maxLen < right - left - 1) {
            start = left + 1;
            maxLen = right - left - 1;
        }
    }
};

Java因为引用的问题，要声明为类属性；而且Java的字符串类和C++的不同，不能使用下标形式，只能用charAt格式；Java的substring第二个参数是结尾下标加一(可数组越界)，C++的substr的第二个参数是长度：

class Solution {
    int start = 0, maxLen = 0;
    public String longestPalindrome(String s) {
        if (s.length() < 2) {
            return s;
        }
        int i = 0, n = s.length();
        for (i = 0; i < n - 1; ++i) {
            search(s, i, i);
            search(s, i, i + 1);
        }
        
        return s.substring(start, maxLen + start);
    }
    public void search(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            --left;
            ++right;
        }
        if (right - left - 1 > maxLen) {
            maxLen = right - left - 1;
            start = left + 1;
        }
    }
}

当然还有不用函数的写法，具体看大神的博客。
也可以用动态规划的思路来解，声明一个二维dp数组，dp[i][j]表示以第j个字符开头并以第i个字符结尾的子字符串是否是回文字符串，是为1，不是为0，这样我们可以知道回文字符串的长度和起点i。状态转移函数是：dp[i][j]首先判断s[i] == s[j]，如果是，那么判断i是否等于j，若满足，字符串就是一个字符，是为回文，否则要满足dp[i - 1][j + 1] == 1。

dp[i, j] = 1                                               if i == j

           = s[i] == s[j]                                if j = i + 1

           = s[i] == s[j] && dp[i + 1][j - 1]    if j > i + 1      

class Solution {
    public String longestPalindrome(String s) {
        if (s.isEmpty()) return "";
        int n = s.length(), left = 0, len = 1;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; ++i) {
            dp[i][i] = 1;
            for (int j = 0; j < i; ++j) {
        //dp[j][i] = (s.charAt(i) == s.charAt(j) && (i - j < 2 || dp[j + 1][i - 1]));
                if (s.charAt(i) == s.charAt(j) && (i - j < 2 || dp[j + 1][i - 1] != 0))
                    dp[j][i] = 1;
                else dp[j][i] = 0;
                if (dp[j][i] != 0 && len < i - j + 1) {
                    len = i - j + 1;
                    left = j;
                }
            }
        }
        return s.substring(left, len + left);
    }
}

使用动态规划的运行时间竟然远远超过第一种解法的运行时间。
还有一种马拉车算法 Manacher's Algorithm，将时间复杂度提升到了 O(n) ，有关于它的学习 Manacher's Algorithm马拉车算法，这题如何使用这个算法也看博客。

---

参考资料:

1. LeetCode原题
2. [LeetCode] 5. Longest Palindromic Substring grandyang/leetcode#5