CVTE技术面试(找字符串中的最长回文子串)

发表于 | 分类于

CVTE技术面——最长回文串

我面的是C++岗位，说是技术面，但实际上问的很少有C++相关的内容。更主要的是围绕项目来问问题，但因为我的项目没有与C++相关的，因此面试官也问不出什么。印象比较深刻的是问了一道算法题，即从字符串中找到最长的回文串。而我当时只想到了最简单暴力的O(n^3)的做法。下面把这道题详细说明如下：

回文串，即一个字符串正读和倒着读均一样，如aba。而判断回文串的方法很简单，只需用一次循环，依次将第一个字符和最后一个字符，第二个字符和倒数第二个字符依次进行比较，以此类推。若均相等，则为回文串。

https://blog.csdn.net/csdnnews/article/details/82920678 漫画解题

暴力解法O(n^3)

找出这个字符串的所有子串，然后依次判断该子串是否为回文。这种方法一共要O(n^3)的时间，空间则为O(1)。很明显，时间复杂度过高。

动态规划O(n^2)

设状态dp[j][i]表示索引j到索引i的子串是否是回文串。则转移方程为：
image.png

则dp[j][i]为true时表示索引j到索引i形成的子串为回文子串，且子串起点索引为j,长度为i - j + 1。

dp[i][j]的递推公式可以这么表述：

  1. 首先，对dp的对角线元素初始化为1，也就是当i == j时，dp[i][j] = 1。显然，每个单独的字符其实就是一个长度为1的回文串。

  2. 当j-i == 1时，若s[i] == s[j]，则dp[i][j]=2，否则dp[i][j] = 0. 解释如下：当j-i==1时，若s[i]=s[j]，则s[i]和s[j]可以组成一个长度为2的回文串。若s[i]!=s[j]，显然他们不可能组成回文串，dp[i][j]=0.

  3. 当j-i >= 2时: (1)若s[i]==s[j]: 若dp[i+1][j-1]>0，则dp[i][j]=dp[i+1][j-1]+2；否则dp[i][j]=0。 (2)若s[i] != s[j]: dp[i][j]=0.

解释如下：如果s[i]==s[j]，表明这个子串有可能是回文串。当去头去尾后它是回文串时，就可以在去头去尾的回文串长度基础上+2，得到它的长度。如果去头去尾后不是回文串，则该子串一定不是回文串，回文串长度只能是0.

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
#include <iostream>
#include <cstring>
using namespace std;

string longestPalindrome(string s){
    const int n = s.size();
    bool dp[n][n];
    memset(dp, 0, sizeof(dp));

    int maxlen = 1;  //保存最长回文子串长度
    int start = 0;   //保存最长回文子串起点
    for(int i=0; i<n; i++){
        for(int j=0; j<=i; j++){
            if(i - j < 2){
                dp[j][i] = (s[i] == s[j]);
            }
            else{
                dp[j][i] = (s[i] == s[j] && dp[j+1][i-1]);
            
            }
            if(dp[j][i] && maxlen < i - j + 1) {
                maxlen = i - j + 1;
                start = j;
            }
        }
    }
}

中心扩展法

中心扩展就是把给定的字符串的每一个字母当做中心，向两边扩展，这样来找最长的子回文串。算法复杂度为O(n^2)。
需要考虑两种情况：长度为奇数的回文串，比如a, aba, abcba；长度为偶数的回文串，比如aa, abba

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
#include <iostream>
#include <cstring>
using namespace std;

string longestPalindrome(string &s){
    const int len = s.size();
    int maxlen = 1; //保存最长回文子串长度
    int start = 0;  //保存最长回文子串起点

    for(int i=0; i<len; i++){ //求长度为奇数的回文串
        int j = i - 1, k = i + 1;
        while(j >= 0 && k < len && s.at(j) == s.at(k)){ //at函数表示返回对应下标的元素引用
            if(k-j+1 > maxlen){
                maxlen = k - j + 1;
                start = j;
            }
            j--;
            k++;
        }
    }

    for(int i=0; i<len; i++){ //求长度为偶数的回文串
        int j = i, k = i + 1;
        while(j >= 0 && k < len && s.at(j) == s.at(k)){
            if(k - j + 1 > maxlen){
                maxlen = k - j + 1;
                start = j;
            }
            j--;
            k++;
        }
    }

    return s.substr(start, maxlen);
}