647. 回文子串

原题链接：

647. 回文子串

https://leetcode.cn/problems/palindromic-substrings/description/

完成情况：

解题思路：

_647回文子串_dp法

这段代码是一个用于计算给定字符串中回文子串数量的解决方案。代码中定义了一个Solution类，其中包含一个countSubstrings方法，该方法接收一个字符串s作为参数，并返回回文子串的数量。

代码首先将输入字符串s转换为字符数组chars，并获取字符串长度len。然后创建一个二维布尔数组dp，用于记录字符串中各个子串是否为回文串。接着初始化一个变量result用于存储回文子串的数量。

代码使用动态规划的思想，在双重循环中遍历字符串中所有可能的子串。对于每个子串，检查其首尾字符是否相同，如果相同则根据不同情况更新result和dp数组：

• 情况一：子串长度为1，直接将回文子串数量加一，并标记dp[i][j]为true。
• 情况二：子串长度为2，同样将回文子串数量加一，并标记dp[i][j]为true。
• 情况三：子串长度大于2，且去掉首尾字符后的子串为回文串，也将回文子串数量加一，并标记dp[i][j]为true。

最终返回result作为回文子串的总数量。

_647回文子串_简易dp法

这段代码实现了一个计算给定字符串中回文子串数量的功能。以下是代码的解释：

• 定义了一个Solution类，其中包含一个公共方法countSubstrings，该方法接受一个字符串s作为参数，并返回回文子串的数量。
• 创建了一个二维布尔数组dp，用于记录字符串s中的回文子串。
• 初始化变量res为0，用于存储回文子串的数量。
• 使用两层循环遍历字符串s的所有可能子串，从后往前遍历i，从i到字符串末尾遍历j。
• 在每一对(i, j)中，如果s的第i个字符等于第j个字符，并且(j - i <= 1)或者子串s[i+1:j-1]也是回文串（即dp[i+1][j-1]为真），则将res加一，并将dp[i][j]标记为真。
• 最后返回res，即字符串s中回文子串的数量。

这段代码通过动态规划的方法计算字符串中的回文子串数量，时间复杂度为$O(n^2)$，其中n为字符串s的长度。

_647回文子串_中心扩展法

这段代码是一个Java解决方案类，其中的方法countSubstrings用于计算给定字符串s中的回文子串数量。

• 首先，代码会检查输入字符串s是否为空或长度小于1，若是则直接返回0。
• 然后，通过遍历字符串s的所有可能中心点（总共有$2\times \text{len}-1$个中心点），向两边扩散来判断是否是回文子串。
• 对于每个中心点，有两种情况：一种是left == right，另一种是right = left + 1，这两种情况的回文中心不同。
• 在扩散过程中，如果发现当前子串是回文串，则记录数量ans并继续向两边扩散。
• 最终返回回文子串的数量ans。

这段代码利用中心扩散法来快速计算回文子串的数量，通过遍历所有可能的中心点，从中心向两边扩散，判断是否是回文串。

_647回文子串_Manacher算法

这段代码是一个解决回文子串数量问题的算法。下面是对代码的清晰、简洁和易读的解释：

1. 首先，将输入字符串$s$进行预处理，构建一个新的字符串$t$。在$t$的开头插入字符’KaTeX parse error: Expected 'EOF', got '#' at position 4: '和'#̲'，在sKaTeX parse error: Expected 'EOF', got '#' at position 11: 的每个字符后面插入'#̲'，并在t$的末尾插入字符’!'。
2. 初始化一个长度为$n$的数组$f$，以及三个变量$iMax$、$rMax$和$ans$，分别用来记录当前回文子串的中心、右边界和回文子串数量。
3. 从索引1开始遍历字符串$t$，对于每个位置$i$：
   • 计算$f[i]$的初始值，如果$i$在$rMax$的范围内，则$f[i]$取$i$关于$iMax$对称位置和$rMax-i$的较小值，否则$f[i]=1$。
   • 从当前位置$i$向两边进行中心拓展，直到不再是回文串为止，更新$f[i]$的值。
   • 动态更新$iMax$和$rMax$，确保包含当前最右边界的最大回文子串。
   • 统计回文子串数量，贡献为$(f[i]-1)/2$的上取整值。
4. 返回最终的回文子串数量$ans$。

整体来说，这段代码利用了中心拓展法来统计给定字符串中的回文子串数量。

参考代码：

_647回文子串_dp法

package 代码随想录.动态规划;

public class _647回文子串_dp法 {
    /**
     *
     * @param s
     * @return
     */
    public int countSubstrings(String s) {
        // 给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
        // 按下标为唯一标识符，不考虑字符的重复性，同时要保证是连续的。
        char[] chars = s.toCharArray();
        int len_chars = chars.length;
        boolean [][] dp = new boolean[len_chars][len_chars];
        int result = 0;
        for (int i = len_chars  -  1;i>=0;i--){
            for (int j = i;j<len_chars;j++){
                if (chars[i] == chars[j]){
                    if (j - i<=1){
                        result++;
                        dp[i][j] = true;
                    }else if (dp[i+1][j-1]){
                        result++;
                        dp[i][j]  = true;
                    }
                }
            }
        }
        return result;
    }
}

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

_647回文子串_简易dp法

package 代码随想录.动态规划;

public class _647回文子串_简易dp法 {
    /**
     *
     * @param s
     * @return
     */
    public int countSubstrings(String s) {
        // 给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
        // 按下标为唯一标识符，不考虑字符的重复性，同时要保证是连续的。
        char[] chars = s.toCharArray();
        int len_chars = chars.length;
        boolean [][] dp = new boolean[len_chars][len_chars];
        //也可以直接调s.length(),s.chatAt(i)方法直接获取。

        int res = 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) && (j-i <= 1 || dp[i+1][j-1])){
                    res++;
                    dp[i][j] = true;
                }
            }
        }
        return res;
    }
}

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

_647回文子串_中心扩展法

package 代码随想录.动态规划;

public class _647回文子串_中心扩展法 {
    /**
     *
     * @param s
     * @return
     */
    public int countSubstrings(String s) {
        // 给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
        // 按下标为唯一标识符，不考虑字符的重复性，同时要保证是连续的。
        int len_s = s.length(),res = 0;
        if (s == null || len_s < 1 ){
            return 0;
        }
        //总共有【2 * len - 1】个中心店
        for (int i = 0; i < 2 * len_s - 1; i++){
            //通过遍历每个回文中心，向两边扩散，并判断为是否回文字串
            //有两种情况，left == right ,,, right = left + 1 ,,,这两种回文中心是不一样的。
            int left = i/2,right = left + i % 2;
            while (left >= 0 && right < len_s && s.charAt(left) == s.charAt(right)){
                //如果当前是一个回文串，则记录效量
                res++;
                left--;
                right++;
            }
        }
        return res;
    }
}

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

_647回文子串_Manacher算法

package 代码随想录.动态规划;

public class _647回文子串_Manacher算法 {
    /**
     *
     * @param s
     * @return
     */
    public int countSubstrings(String s) {
        // 给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
        // 按下标为唯一标识符，不考虑字符的重复性，同时要保证是连续的。
        int len_s = s.length();
        StringBuilder sb_s = new StringBuilder("s#");
        for (int i = 0; i < len_s; i++) {
            sb_s.append(s.charAt(i));
            sb_s.append("#");
        }
        int len_sb_s = sb_s.length();
        sb_s.append('!');
        int [] dp = new int [len_sb_s];
        int iMax = 0,rMax = 0,res = 0;
        for (int i = 1;i<len_sb_s;i++){
            //初始化 f[i]
            dp[i] = i <= rMax ? Math.min(rMax - i + 1,dp[2*iMax - i]) : 1;
            //中心扩展
            while (sb_s.charAt(i + dp[i]) == sb_s.charAt(i - dp[i])){
                ++dp[i];
            }
            //动态维护iMax 和 rMax
            if (i + dp[i] - 1 > rMax){
                iMax = i;
                rMax = i + dp[i] - 1;
            }
            //统计答案，当前贡献为（f[i] - 1）/2 向上取整
            res += dp[i] / 2;
        }
        return res;
    }
}

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

错误经验吸取