Leetcode-最长回文子串

· ☕ 2 分钟 · 👻 Victor
🏷️
  • #C++
  • #leetcode
  • 问题描述

    给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

    示例 1:

    输入: "babad"
    输出: "bab"
    注意: "aba" 也是一个有效答案。
    

    示例 2:

    输入: "cbbd"
    输出: "bb"
    

    解答

    使用动态规划,把原来的字符串倒置,然后找最长的公共子串就可以了。例如 S = “caba” ,S = “abac”,最长公共子串是 “aba”,所以原字符串的最长回文串就是 “aba”。其中求最大公共子串就是使用动态规划的方法。

    示意图:

    动态规划

    • S[i]==S[j]时,矩阵arr[i][j]=arr[i-1][j-1]+1;特殊情况i、j为0时arr[i][j]=1
    • 其他情况跳过。

    另外,还需要考虑最长公共子串不是回文的情况,只需要判断翻转前后的末尾字符下标是否一样即可,比如 S="caba”,S'="abac” ,S’ 中 aba 的下标是 0 1 2 ,倒置前是 3 2 1,和 S 中 aba 的下标符合,所以 aba 就是我们需要找的。当然我们不需要每个字符都判断,我们只需要判断末尾字符就可以。

    代码实现

     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
    
    #include <iostream>
    #include <algorithm>
    class Solution
    {
    public:
        string longestPalindrome(string s)
        { //暴力法
            int len = s.length();
            if (len <= 1)
                return s;
            std::string r;
            std::string real = s;
            reverse(s.begin(), s.end());
            std::string reverse = s;
            int arr[len][len];
            for (int i = 0; i < len; ++i)
                for (int j = 0; j < len; ++j)
                    arr[i][j] = 0;
            int maxLen(0), maxEnd(0);
            for (int i = 0; i < len; ++i)
            {
                for (int j = 0; j < len; ++j)
                {
                    if (real[i] == reverse[j])
                    {
                        if (i == 0 || j == 0)
                            arr[i][j] = 1;
                        else
                        {
                            arr[i][j] = arr[i - 1][j - 1] + 1;
                        }
                    }
                    if (arr[i][j] > maxLen)
                    {
                        int beforeindex = len - 1 - j;
                        if ((beforeindex + arr[i][j] - 1) == i)
                        {
                            maxLen = arr[i][j];
                            maxEnd = i;
                        }
                    }
                }
            }
            return real.substr(maxEnd - maxLen + 1, maxLen);
        }
    };
    

    结果:

    result

    分享

    redisread
    作者
    Victor
    Full Stack