LeetCode，

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

Example 1:                                                        Example 2:

Input: "babad"                            Input: "cbbd"
Output: "bab"                             Output: "bb"
Note: "aba" is also a valid answer.

方法一：中心扩展  （beats 84.72%）

    这道题如果暴力求解的话太麻烦了，这种回文问题，用从中心逐渐向左右两边扩展的方式进行计算会快很多，值得注意的是，回文问题中，“aba”和“abba”不是一种类型，前一种是以一个字符为中心的对称，后一种是以两个相同字符为中心的对称，两种中心方式都要考虑。我的代码如下：

string longestPalindrome(string s)
{
    int len = s.length();
    if (len == 1 || len == 0)
        return s;
    int max_len = 1, start = -1;    // 最长回文string的起始位置，max_len是最长回文长度
    for (int i = 0; i < len; i++)
    {
        int l = i - 1, r = i + 1;       // left, right
        // 把一个字符作为中心
        while (l >= 0 && r <= len - 1 && s[l] == s[r]){ --l; ++r; }
        if (r - l - 1 > max_len)
        {
            max_len = r - l - 1;
            start = l + 1;
        }
        
        if (i != len - 1 && s[i] == s[i + 1])           
        {
            l = i - 1, r = i + 2;
            // 两个相同字符作为中心
            while (l >= 0 && r <= len - 1 && s[l] == s[r]){ --l; ++r; }
            if (r - l - 1 > max_len)
            {
                max_len = r - l - 1;
                start = l + 1;
            }
        }
    }
    if(start == -1)     // 当没有回文子串的时候，随便返回一个就行，为保证不会越界，返回第一个就行
        return string() + s[0];
    return s.substr(start, max_len);
}

    就是从左往右，以所有位置为中心进行扩展尝试，如果有两个连着一样的，以这两个并列为中心，向左右进行扩展尝试，找出最长的长度，以及最长回文子串的开头，这样利用substr就可以得到最长回文子串了（如果有两个以上连着相同的情况并不用考虑，因为三个可以看成1个扩展了一层，4个可以看成2个扩展了一层，and so on）。

方法二：DP  （beats 44.34%）

    一个简单的改进暴力算法的想法就是，比如“cabac”这种情况下，我们已经知道“aba”是回文的了，只需要判断左右两边是不是，就可以知道整个string是不是了（和中心扩展思想一样，但是需要O(N ^ 2)的空间）。也就是说比如我们设 dp[i][j] 为 true 表示 s 从 i 到 j 是回文的，那么要求就是 dp[i + 1][j - 1] 为 true，且 s[i] == s[j]。

    最开始我们知道 dp[i][i] 对所有 i 来说都成立，然后如果 s[i] == s[i + 1]，那么 dp[i][i + 1] 就是true。

    比如 s 长度为 len，基于这两点就可以创建一个 len * len 大小的矩阵，并且对矩阵进行初始化，然后一步一步计算矩阵每个位置上的值，最后找出 j - i 最大的位置。直接照着网上的solution写的：

string longestPalindrome(string s)
{
    int n = s.length();
    int start = 0, max_len = 1;
    bool table[1000][1000] = {false};   // 这样初始化其实不行（只能给table[0][0]赋值），不过默认是false
    for (int i = 0; i < n; i++)
        table[i][i] = true;
    for (int i = 0; i < n - 1; i++)
    {
        if (s[i] == s[i+1])
        {
            table[i][i+1] = true;
            start = i;
            max_len = 2;
        }
    }
    for (int len = 3; len <= n; len++)
    {
        for (int i = 0; i < n - len + 1; i++)
        {
            int j = i + len - 1;
            if (s[i] == s[j] && table[i + 1][j - 1])    // 谁先谁后感觉区别不大
            {
                table[i][j] = true;
                start = i;
                max_len = len;
            }
        }
    }
    return s.substr(start, max_len);
}

方法三：Manacher's Algorithm  （beats 99.23%）

    做题的时候感觉特别像字符串匹配的KMP算法，感觉这道题肯定有更加高效的算法，只不过是我不知道而已= =。

    果然，LeetCode这道题给出的Solution里提到了只需要O(N)时间（Linear Time）即可完成的算法，叫作“Manacher's Algorithm”。

    这个算法和我最开始的想法一样，就是在每个字符中插入一个特定字符，我想的是“-”，比如“aba”编程 “a-b-a”，这里就是用的“#”，没区别，但是跟我想的不一样的是，字符串的左右两端也扩充了，而且在两个又各加了一个控制符，为了控制便捷，比如“aba”，就变成了“^$#a#b#a#$”。这样做的好处就是，不需要再考虑是单独一个字符为中心，还是两个相同字符为中心，而是在插入“#”后，只需要考虑以单个字符为中心的情况。比如说第一方法中，如果“bb”是中心，那么在这个算法中是，“b#b” 中间的 “#” 为中心，如果是“b”为中心，那这个算法里也就是“b”为中心。

    这个不是这个算法的核心，这个算法的核心思想就是要跳过不必要的重复判断。

   算法的思想是，先对字符串进行上述处理，然后创建一个和新的字符串同样大小的数组，比如说叫P，P[i] 表示以第i位为中心的最长回文串的一半的长度，也可以理解为以这个圆为圆心的半径。直接用Solution里的原图看看数组的值：

比如说，“habcbap”，转换之后是“^$#h#a#b#c#b#a

共2页: 上一页12下一页

相关文章

暂无相关文章