【算法挨揍日记】day34——647. 回文子串、5. 最长回文子串

落日映苍穹つ 2024-02-17 12:58 68阅读 0赞

## 647. 回文子串 ##

[647. 回文子串][647.]

### 题目描述： ###

给你一个字符串 `s` ，请你统计并返回这个字符串中 **回文子串** 的数目。

**回文字符串** 是正着读和倒过来读一样的字符串。

**子字符串** 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。![bad9fdf6c8db49d8bb2deb624726724d.png][]

### 解题思路： ###

算法思路：

我们可以先「预处理」⼀下，将所有⼦串「是否回⽂」的信息统计在  dp  表⾥⾯，然后直接在表

⾥⾯统计  true  的个数即可。

1.  状态表⽰：

为了能表⽰出来所有的⼦串，我们可以创建⼀个  n \* n  的⼆维  dp  表，只⽤到「上三⻆部分」

即可。

其中，  dp\[i\]\[j\]  表⽰：  s  字符串  \[i, j\]  的⼦串，是否是回⽂串。

2.  状态转移⽅程：

对于回⽂串，我们⼀般分析⼀个「区间两头」的元素：

i.  当  s\[i\] != s\[j\]  的时候：不可能是回⽂串，  dp\[i\]\[j\] = 0  ；

ii.  当  s\[i\] == s\[j\]  的时候：根据⻓度分三种情况讨论：

•  ⻓度为  1  ，也就是  i == j  ：此时⼀定是回⽂串，  dp\[i\]\[j\] = true  ；

•  ⻓度为  2  ，也就是  i + 1 == j  ：此时也⼀定是回⽂串，  dp\[i\]\[j\] = true  ；

•  ⻓度⼤于  2  ，此时要去看看  \[i + 1, j - 1\]  区间的⼦串是否回⽂：  dp\[i\]\[j\]

= dp\[i + 1\]\[j - 1\]  。

综上，状态转移⽅程分情况谈论即可。

3.  初始化：

因为我们的状态转移⽅程分析的很细致，因此⽆需初始化。

4.  填表顺序：

根据「状态转移⽅程」，我们需要「从下往上」填写每⼀⾏，每⼀⾏的顺序⽆所谓。

5.  返回值：

根据「状态表⽰和题⽬要求」，我们需要返回  dp  表中  true  的个数。

### 解题代码： ###

class Solution {
    public:
        int countSubstrings(string s) {
            int n=s.size();
            vector<vector<bool>>dp(n,vector(n,false));
            for(int i=n-1;i>=0;i--)
            {
                for(int j=i;j<n;j++)
                {
                    if(s[i]==s[j])
                    {
                        if(i==j)dp[i][j]=true;
                        else if(i+1==j)dp[i][j]=true;
                        else dp[i][j]=dp[i+1][j-1];
                    }
                }
            }
            int ret=0;
            for(int i=0;i<n;i++)
            {
                for(int j=i;j<n;j++)
                {
                    if(dp[i][j]==true)
                    ret++;
                }
            }
            return ret;
        }
    };

## 5. 最长回文子串 ##

[5. 最长回文子串][5.]

### 题目描述： ###

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

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。![972f6921277340b2b6a41d00be3789cc.png][]

### 解题思路： ###

[647. 回文子串![icon-default.png?t=N7T8][icon-default.png_t_N7T8]https://image.dandelioncloud.cn/pgy_files/images/2024/02/06/35adf063361e4ae7a07733161745ec0b.png][647.]

在647题的基础上遍历所有dp表中为true的初始位置和长度

### 解题代码： ###

class Solution {
    public:
        string longestPalindrome(string s) {
            int n=s.size();
            vector<vector<bool>>dp(n,vector(n,false));
            for(int i=n-1;i>=0;i--)
            {
                for(int j=i;j<n;j++)
                {
                    if(s[i]==s[j])
                    {
                        if(i==j)dp[i][j]=true;
                        else if(i+1==j)dp[i][j]=true;
                        else dp[i][j]=dp[i+1][j-1];
                    }
                }
            }
            int length=1;
            int begin=0;
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<n;j++)
                if(dp[i][j]==true&&length<j-i+1)
                {
                    length=max(j-i+1,length);
                    begin=i;
                }
            }
            return s.substr(begin,length);
        }
    };

###  ###

[647.]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/06/35adf063361e4ae7a07733161745ec0b.png
[bad9fdf6c8db49d8bb2deb624726724d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/06/ffcf355d08464e86922c893d23fe0d14.png
[5.]: https://leetcode.cn/problems/longest-palindromic-substring/
[972f6921277340b2b6a41d00be3789cc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/06/a47c4c8eacb348bb9fa73527cb5ae725.png
[icon-default.png_t_N7T8]: https://csdnimg.cn/release/blog_editor_html/release2.3.6/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=N7T8