5. 最长回文子串

题目链接

解析

对于一个长度为\(n\)的字符串s而言,其共有\(O(n^2)\)个子字符串substr(\(n^2\)个开始-结束对),而对于每个子字符串substr而言,需\(O(n)\)的时间复杂度来核对该子字符串是否是回文字符串。
所以暴力求解的复杂度为\(O(n^3)\),应该是不符合题目要求的。

那如何降低复杂度呢,动态规划!
将核对的时间复杂度从\(O(n)\)降为\(O(1)\)。

那如何实现\(O(1)\)时间判定一个子字符串substr是否是回文字符串呢?仔细观察回文字符串的性质可以发现:

对于子字符串substr而言,

  1. 若长度为1,则substr是回文字符串。
  2. 若长度为2,且substr[0]==substr[1],则substr是回文字符串。
  3. 若长度为3,则substr是回文字符串的前提是,substr[0]=substr[2],且子字符串substr[1]是回文字符串(由于substr[1]长度为1,肯定是回文字符串)。
  4. 若长度大于3,则substr是回文字符串的前提是,substr的首字符substr[0]等于尾字符substr[length - 1],且去掉首、尾字符的字符串是回文字符串(已求出)。

根据以上4条,就可以在\(O(1)\)的时间内确定substr是否是回文字符串,从而在\(O(n^2)\)的时间内确定s的所有子字符串substr是否是回文字符串。

最终遍历子字符串的长度(由长到短),输出其中一个最长的回文子字符串即可,遍历的时间复杂度为\(O(n^2)\)。

复杂度

实现

C++

class Solution {
public:
    string longestPalindrome(string s) {
        int length = s.length();
        bool flag[1005][1005] = {};  // 用于标识子字符串是否是回文字符串,初始化为0

        // 若长度为1,则是回文字符串。
        for (int i = 0; i < length; i++) {
            flag[i][1] = 1; 
        }

        // 若长度为2,且两个字符相同,则是回文字符串。
        for (int i = 0; i < length - 1; i++) {
            if (s[i] == s[i + 1]) flag[i][2] = 1;
        }

        // 若长度大于等于3,则是回文字符串的前提是,首字符等于尾字符,且去掉首、尾字符的字符串是回文字符串。
        for (int l = 3; l <= length; l++) {
            for (int i = 0; i <= length - l; i++) {
                if (s[i] == s[i + l - 1] && flag[i + 1][l - 2])
                    flag[i][l] = 1;
            }
        }

        // 遍历子字符串的长度(由长到短),输出其中一个最长的回文子字符串即可。
        for (int l = length; l >= 0; l--) {
            for (int i = 0; i < length - 1; i++) {
                if (flag[i][l]) {
                    return s.substr(i, l);
                }
            }
        }
        return s.substr(0, 1);
    }
};
上一篇:slice,subStr,subString区别


下一篇:js-身份证识别性别和出生日期