最长回文子串

Longest Palindromic Substring

思路1: 从中间向两边展开, 分奇偶讨论

1. 循环可以求出长度为2和3的回文子串, 长度为1时需要拎出来处理
   
2. 剩余子串必须大于最长回文的一半, 不然不可能超越当前最长回文
   

解答

Copy 1class Solution {
 2public:
 3    string longestPalindrome(string s) {
 4        auto n = s.length();
 5
 6        string res = s.substr(0, 1);
 7        auto cnt = 1;
 8
 9        for (auto i = 0; i + cnt / 2 < n; ++i)
10        {
11            auto start = 0, newCnt = 0;
12
13            for (auto j = i - 1, k = i + 1; j >= 0 && k < n && s[j] == s[k]; --j, ++k)
14            {
15                start = j;
16                newCnt = k - j + 1;
17            }
18
19            if (newCnt > cnt)
20            {
21                res = s.substr(start, newCnt);
22                cnt = newCnt;
23            }
24
25            for (auto j = i, k = i + 1; j >= 0 && k < n && s[j] == s[k]; --j, ++k)
26            {
27                start = j;
28                newCnt = k - j + 1;
29            }
30
31            if (newCnt > cnt)
32            {
33                res = s.substr(start, newCnt);
34                cnt = newCnt;
35            }
36        }
37        return res;
38    }
39};

思路2: 动态规划

Dynamic programming

DP

已判断过的, 直接拿来用

1. 动态规划的思路中, 对回文片段进行了标记, 数组元素 dp[i][j] 的值, 指示 s[i] 到 s[j] 这一子串是否为回文
   
2. 计算回文片段的方式有两种:
   

   • 常规思路, 逐渐增加片段长度, 判断增加后的片段是否为回文
     

   • 逐渐增加参与计算的子串长度, 在已有的基础上扩张标记
     

计算回文片段

1. 常规思路: 控制回文片段的长度, 从1取到n
   

2. 在已有基础上扩张
   

   • 外层循环: i 从0到 n - 1
     

   • 内层循环: j 从0到 i - 1
     

   • 已预设长度为1时为回文片段
     

   • 当长度不大于3时, 首尾元素相等也为回文片段
     

   • 长度大于3时, 要求首尾元素相等, 且中间部分为回文片段
     

   • 因为是在已有基础上进行扩张, 上一轮外层循环已作出中间部分是否为回文的判断, 可以直接拿来用
     

   初始状态
   

   ELEMENT        * * * * * * * * * * * *
   SAVED INDEX    j         i

   i - j 为1
   

   INDEX          0 1 2 3 4 5
   ELEMENT        * * * * * * * * * * * *
   SAVED INDEX            j i

   i - j 为2
   

   INDEX          0 1 2 3 4 5
   ELEMENT        * * * * * * * * * * * *
   SAVED INDEX          j   i

   i - j 为3
   

   INDEX          0 1 2    3      4        5
   ELEMENT        * * *    *      *        * * * * * * *
   SAVED INDEX        j    j + 1  i - 1    i

解答

1. 常规思路
   

   Copy 1class Solution {
    2public:
    3    string longestPalindrome(string s) {
    4        auto n = s.length();
    5        auto cnt = 1, start = 0;
    6
    7        vector<vector<bool>> dp(n, vector<bool>(n, false));
    8        bool flag1 = false, flag2 = false;
    9        for (auto i = 0; i < n; ++i)
   10        {
   11            dp[i][i] = true;
   12            if (i + 1 < n && s[i] == s[i + 1])
   13            {
   14                dp[i][i + 1] = true;
   15                if (!flag2 && !flag1)
   16                {
   17                    flag1 = true;
   18                    start = i;
   19                    cnt = 2;
   20                }
   21            }
   22            if (i + 2 < n && s[i] == s[i + 2])
   23            {
   24                dp[i][i + 2] = true;
   25                if (!flag2)
   26                {
   27                    flag2 = true;
   28                    start = i;
   29                    cnt = 3;
   30                }
   31            }
   32        }
   33
   34        for (auto j = 3; j < n; ++j)
   35        {
   36            bool flag = false;
   37            for (auto i = 0; i + j < n; ++i)
   38            {
   39                if (s[i] == s[i + j] && dp[i + 1][i + j - 1])
   40                {
   41                    dp[i][i + j] = true;
   42
   43                    if (!flag)
   44                    {
   45                        flag = true;
   46                        start = i;
   47                        cnt = j + 1;
   48                    }
   49                }
   50            }
   51        }
   52
   53        return s.substr(start, cnt);
   54    }
   55};

2. 扩张
   

   Copy 1class Solution {
    2public:
    3    string longestPalindrome(string s) {
    4        auto n = s.length();
    5        auto cnt = 1, start = 0;
    6
    7        vector<vector<bool>> dp(n, vector<bool>(n, false));
    8        for (auto i = 0; i < n; ++i)
    9        {
   10            dp[i][i] = true;
   11            for (auto j = 0; j < i; ++j)
   12            {
   13                if (s[j] == s[i] && (i - j <= 2 || dp[j + 1][i - 1]))
   14                {
   15                    dp[j][i] = true;
   16                    auto newCnt = i - j + 1;
   17                    if (newCnt > cnt)
   18                    {
   19                        cnt = newCnt;
   20                        start = j;
   21                    }
   22                }
   23            }
   24        }
   25        return s.substr(start, cnt);
   26    }
   27};