LeetCode-647. 回文子串

逃离我推掉我的手 2024-03-24 12:57 84阅读 0赞

#### 目录 ####

*   *  动态规划

题目来源  
[647. 回文子串][647.]

### 动态规划 ###

*  1.确定dp数组（dp table）以及下标的含义

看回文串的性质  
![在这里插入图片描述][38325c4f5ccc46ba85c597e9c8c7ca99.png]  
我们在判断字符串S是否是回文，那么如果我们知道 s\[1\]，s\[2\]，s\[3\] 这个子串是回文的，那么只需要比较 s\[0\]和s\[4\]这两个元素是否相同，如果相同的话，这个字符串s 就是回文串。  
布尔类型的dp\[i\]\[j\]：表示区间范围\[i,j\] （注意是左闭右闭）的子串是否是回文子串，如果是dp\[i\]\[j\]为true，否则为false。

*  2.确定递推公式

在确定递推公式时，就要分析如下几种情况。  
整体上是两种，就是s\[i\]与s\[j\]相等，s\[i\]与s\[j\]不相等这两种。  
**当s\[i\]与s\[j\]不相等，那没啥好说的了，dp\[i\]\[j\]一定是false。**  
**当s\[i\]与s\[j\]相等时，这就复杂一些了，有如下三种情况**  
情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串  
情况二：下标i 与 j相差为1，例如aa，也是回文子串  
情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s\[i\]与s\[j\]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp\[i + 1\]\[j - 1\]是否为true。  
以上三种情况分析完了，那么递归公式如下：

if(s.charAt(i) == s.charAt(j)){
        
                        if(j-i<=1){
        
                            ans++;
                            dp[i][j] = true;
                        }else if(dp[i+1][j-1]){
        
                            ans++;
                            dp[i][j] = true;
                         }
                    }
                }

ans就是统计回文子串的数量。

*  3.dp数组如何初始化

dp\[i\]\[j\]可以初始化为true么？ 当然不行，怎能刚开始就全都匹配上了。  
所以dp\[i\]\[j\]初始化为false。

*  4.确定遍历顺序

首先从递推公式中可以看出，情况三是根据dp\[i + 1\]\[j - 1\]是否为true，在对dp\[i\]\[j\]进行赋值true的。

dp\[i + 1\]\[j - 1\] 在 dp\[i\]\[j\]的左下角，如图：  
![在这里插入图片描述][e9b22c2dcf9046f0a66d3749252f11bf.png]  
从下到上，从左到右遍历，这样保证dp\[i + 1\]\[j - 1\]都是经过计算的。  
有的代码实现是优先遍历列，然后遍历行，其实也是一个道理，都是为了保证dp\[i + 1\]\[j - 1\]都是经过计算的。

for(int i = s.length()-1;i>=0;i--){
        
                for(int j = i;j<s.length();j++){
        
                    if(s.charAt(i) == s.charAt(j)){
        
                        if(j-i<=1){
        
                            ans++;
                            dp[i][j] = true;
                        }else if(dp[i+1][j-1]){
        
                            ans++;
                            dp[i][j] = true;
                         }
                    }
                }
            }

*  5.举例推导dp数组

举例，输入：“aaa”，dp\[i\]\[j\]状态如下：

![在这里插入图片描述][07c4d68f475043ea9622db73e2a8dbe3.png]  
代码实现

class Solution {
        
        public int countSubstrings(String s) {
        
            boolean[][] dp = new boolean[s.length()][s.length()];
            int ans = 0;
            for(int i = s.length()-1;i>=0;i--){
        
                for(int j = i;j<s.length();j++){
        
                    if(s.charAt(i) == s.charAt(j)){
        
                        if(j-i<=1){
        
                            ans++;
                            dp[i][j] = true;
                        }else if(dp[i+1][j-1]){
        
                            ans++;
                            dp[i][j] = true;
                         }
                    }
                }
            }
            return ans;   
        }
    }

![在这里插入图片描述][b4cef8b41f174ab99ae01c23615aa087.png]

[647.]: https://leetcode.cn/problems/palindromic-substrings/
[38325c4f5ccc46ba85c597e9c8c7ca99.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/f5859a11af384022b756b2ebe6b0ebe3.png
[e9b22c2dcf9046f0a66d3749252f11bf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/8c96d2af4c724bd683b26563e340513a.png
[07c4d68f475043ea9622db73e2a8dbe3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/beb084ab00a64763b09ef3f1bebff170.png
[b4cef8b41f174ab99ae01c23615aa087.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/bda5d420d250460c862f9e00014090cc.png