leetcode 5. 最长回文子串（C++）

桃扇骨 2023-07-16 02:32 18阅读 0赞

python版——>[leetcode 05：最长回文子串(python)][leetcode 05_python]

# 题目 #

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

示例 1：

输入: “babad”  
输出: “bab”  
注意: “aba” 也是一个有效答案。  
示例 2：

输入: “cbbd”  
输出: “bb”

来源：[5. 最长回文子串 - 力扣（LeetCode）][5. _ - _LeetCode]  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

# 中心扩展法 #

*  把字符串中每个字符作为中心，往两边扩展  
    注意区分奇偶回文子串的区别（即"ada"或"adda"）

代码如下：

class Solution { 
    public:
        string longestPalindrome(string s) { 
            int len = s.length();
            if(len < 2)  return s;
            int maxlen = 1;
            int index = 0;
            for(int i = 0;i < len;i++)
            { 
                int l1 = i;
                int r1 = i;
                //处理奇回文串
                while(l1 >= 0 && r1 < len && s[l1] == s[r1])
                { 
                    l1--;
                    r1++;
                }
                if(maxlen < r1 - l1 - 1)
                { 
                    maxlen = r1 - l1 - 1;
                    index = l1 + 1;
                }
                //处理偶回文串
                int l2 = i;
                int r2 = i + 1;
                while(l2 >= 0 && r2 < len && s[l2] == s[r2])
                {    
                    l2--;
                    r2++;
                }
                if(maxlen < r2 - l2 - 1)
                { 
                    maxlen = r2 - l2 - 1;
                    index = l2 + 1;
                }
            }
           return s.substr(index,maxlen);
        }
    };

结果：  
![在这里插入图片描述][20200317212521211.png]

# 动态规划法 #

*  将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。  
    保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。

代码如下：

class Solution { 
    public:
        string longestPalindrome(string s) { 
            int len = s.length();
            if(len < 2)  return s;
            int maxlen = 1;
            int index = 0;
            //定义二维数组储存从i到j的字符串是否为回文串
            int dp[len][len] = { { 0}};
            for(int r = 1;r < len;r++)
            { 
                for(int l = 0;l < r;l++)
                { 
                    if(s[l] == s[r] && (r - l < 3 || dp[l + 1][r - 1] == 1))
                    { 
                        dp[l][r] = 1;
                        if(maxlen < r - l + 1)
                        { 
                            maxlen = r - l + 1;
                            index = l;
                        }
                    }
                }
            }
            return s.substr(index,maxlen);
        }
    };

结果：  
![在这里插入图片描述][20200317220923359.png]

[leetcode 05_python]: https://blog.csdn.net/nanashi_F/article/details/100111888
[5. _ - _LeetCode]: https://leetcode-cn.com/problems/longest-palindromic-substring
[20200317212521211.png]: /images/20230528/6babb3124f2547818f62ef6e2ce88d2a.png
[20200317220923359.png]: /images/20230528/a0019e4bf91d49a2a0ee533b7ab26513.png