Leetcode-最长回文子串

Leetcode - 0005 - 最长回文子串

1.题目链接 (opens new window)

>
>
>给你一个字符串 `s`，找到 `s` 中最长的回文子串。

2. 思路

• 状态转移方程

  设f[i][j] 表示 字符串 [l, r] 是否为回文子串。则易得状态转移方程为f[i][j] = f[i + 1][j - 1] && (s[i] == s[j])

• 状态初始化

  考虑 字符串长度为1 和 2 时的边界情况，递推前可进行特殊初始化操作

  for(int i = 0; i < len; i ++)
          {
              f[i][i] = true;
              if(i + 1 < len && s[i] == s[i + 1])
              {
                  ans = 2;
                  bg = i;
                  f[i][i + 1] = true;
              }
          }
  

3.代码

string longestPalindrome(string s) {
        bool f[1010][1010] = {false};
        int len = s.size();
        int ans = 1;
        int bg = 0;
        for(int i = 0; i < len; i ++)
        {
            f[i][i] = true;
            if(i + 1 < len && s[i] == s[i + 1])
            {
                ans = 2;
                bg = i;
                f[i][i + 1] = true;
            }
        }
        for(int i = 3; i <= len; i ++)
        {
            for(int j = 0; j + i <= len; j ++)
            {
                //cout << i << " " << j << endl;
                int l = j;
                int r = j + i - 1;
                if(f[l + 1][r - 1] && (s[l] == s[r]))
                {
                    f[l][r] = true;
                    if(i > ans) {ans = i; bg = j;}
                }
            }
        }
        return s.substr(bg, ans);
    }