5. Longest Palindromic Substring

发表于 | 分类于 | |

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

Example:

1
2
3
4
5
6
7
> Input: "babad"
>
> Output: "bab"
>
> Note: "aba" is also a valid answer.
>
>

Example:

1
2
3
4
> Input: "cbbd"
>
> Output: "bb"
>

题意很简单：找最长回文串

一开始想到的想法就是把s反转为s’，然后找s和s’的最长共同子串。所以问题又转化成了经典的LCS（LongestCommonString）。

  • 最长公共子串LCS

    用动态规划来解决LCS问题相对比较简单。时间复杂度是O（n^2），空间复杂度也是O（n^2）。思路如下：

    1. 令dp(i,j)来表示以s1[i],s2[j]结尾时两个串目前最长的共同字串。
    2. 当i,j都非第一个字符时，考虑此时s1[i]==s2[j]是否成立
      1. 若成立，则dp(i,j) = dp(i-1,j-1) + 1 （即二维表左上角格子数值加上1）
      2. 若不成立，则dp(i,j) = 0
    3. 当i,j有一个为首字符（即 i==0||j==0 ）时，依旧考虑s1[i]==s2[j]是否成立
      1. 若成立，dp(i,j) = 1 （因为前面没有字符了）
      2. 若不成立，dp(i,j) = 0
    4. 用longest来维护整个过程的最大值

具体实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
//
// Created by chaopengz on 2017/9/20.
//
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    string longestPalindrome(string s1) {
        int dp[1005][1005];
        string s2 = "";
        for (int l = s1.size() - 1; l >= 0; l--) {
            s2 += s1[l];
        }
        int lenS1 = s1.size(), lenS2 = s2.size();
        int longest = 0, endi;

        for (int i = 0; i < lenS1; ++i) {
            for (int j = 0; j < lenS2; ++j) {

                if (i && j) {//不在首行和首列的时候
                    if (s1[i] == s2[j]) {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    } else {
                        dp[i][j] = 0;
                    }
                } else {//首行和首列初始化
                    if (s1[i] == s2[j]) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = 0;
                    }

                }
                if (dp[i][j] > longest) {
                    longest = dp[i][j];
                    endi = i;
                }
            }
        }
        string res = "";
        for (int k = 0; k < longest; ++k) {
            res += s1[endi--];
        }
        return res;
    }
};

以上代码过了样例，但是交上去却发现WA了。

对比LeetCode给出的出错的输入数据，发现上面的想法是有瑕疵的。例如下面的例子：

  • s1=”abcdfcba”

这样子反转后为：

  • s2=”abcfdcba”

s1和s2的最长公共子串为abc，但是abc并不是回文串，那么问题出在哪儿了呢？最主要就是在s2找出的共同子串并不在s1对应的位置上。所以，需要对上述想法进行修正加强，在更新最长子串时，要判断这个子串是否在s1对应的位置上，即

1
s1[i - dp[i][j] + 1] == s2[j]

完整AC的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    string longestPalindrome(string s1) {
        int dp[1005][1005];
        string s2 = "";
        for (int l = s1.size() - 1; l >= 0; l--) {
            s2 += s1[l];
        }
        int lenS1 = s1.size(), lenS2 = s2.size();
        int longest = 0, endi;

        for (int i = 0; i < lenS1; ++i) {
            for (int j = 0; j < lenS2; ++j) {

                if (i && j) {//不在首行和首列的时候
                    if (s1[i] == s2[j]) {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    } else {
                        dp[i][j] = 0;
                    }
                } else {//首行和首列初始化
                    if (s1[i] == s2[j]) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = 0;
                    }
                }
                
                if (dp[i][j] > longest && s1[i - dp[i][j] + 1] == s2[j]) {//更新的时候要加强条件，判断是否为s1和s2对应的子串
                    longest = dp[i][j];
                    endi = i;
                }
            }
        }
        string res = "";
        for (int k = 0; k < longest; ++k) {
            res += s1[endi--];
        }
        return res;
    }
};