[Leetcode][第647题][JAVA][回文子串][动态规划][中心扩展][Manacher 算法]

我会带着你远行 2022-11-29 05:38 163阅读 0赞

#### 【问题描述】\[中等\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]

#### 【解答思路】 ####

###### 1. 暴力 ######

首先明确如何判断一个字符串是否为回文字符串。第一个字符与最后一个字符相同，第二个字符与倒数第二个字符相同…关于中心位置轴对称。  
本题要求一共有多少个回文子串，那么就需要判断，索引\[i, j\]的子串是不是回文子串，遍历所有这样\[i, j\]进行判断就可以找到回文子串的总数。这是暴力的做法。  
首先如何判断\[i, j\]的子串是回文串，根据定义来判断即可。  
定义boolean isPalindrome(char\[\] chars, int start, int end)，第一个参数为原字符串的字符数组表示，第二第三个参数分别是字串的开始与结束索引。  
在区间\[start, end\]上进行双指针的扫描，将关于中心位置对应的字符进行比较，如果发现有不相等说明不是回文子串。  
循环结束没有发现对应位置不相等的字符，说明是回文串。  
主函数中  
外循环的i表示子串的长度，子串最长为s.length()，所以循环的条件为i <= s.length()。从长度2开始是因为，长度为1的子串都是回文子串，一共有s.length()个，最后加上即可。  
内循环j表示子串的开始索引，那么其结束索引为j + i - 1。调用函数isPalindrome进行判断。  
最后返回result + s.length()，将长度为1的子串都是回文子串的计数也算进行。

**时间复杂度：O(N3) 空间复杂度：O(1)**

public int countSubstrings(String s) { 
            char[] chars = s.toCharArray();
            int result = 0;
            for (int i = 2; i <= s.length(); i++) { 
                for (int j = 0; j + i - 1 < s.length(); j++)
                    if (isPalindrome(chars, j, j + i - 1))
                        result++;
            }
            return result + s.length();
        }
    
        private boolean isPalindrome(char[] chars, int start, int end) { 
            for (int i = start, j = end; j > i; i++, j--) { 
                if (chars[i] != chars[j])
                    return false;
            }
            return true;
        }

###### 2. 中心扩展 ######

回文字符串关于中心对称，这个中心既可以是一个字符（比如子串的长度为奇数时），也可以是两个字符的中间（比如子串的长度为偶数时）。那么对于长度为n的字符串，其子串的中心一共有\*\*n+（n-1）\*\*个，n个是字母，n-1个是两个字母的间歇。  
我们需要找到每一个可能的对称中心有能向外扩展出多少个回文子串。要想办法表示每一个回文中心，外扩的方式都一样。  
回文中心与子串的奇偶性有关，想必要分情况讨论。  
如果子串的长度为奇数，那么第一个子串只有一个字符，其左边界left与右边界right相等。  
如果子串的长度为偶数，那么第一个子串有两个字符，其左边界left与右边界right的关系为right = left + 1。  
所以可以通过奇偶性来控制初始时left与right的关系。  
循环 for (int i = 0; i < chars.length \* 2 - 1; i++)，i表示每一个可能的回文中心，通过i的奇偶性来设置初始的left, right。内循环进行外扩，首先保证索引不超过数组边界，其次当前判断的两个字符相等。否则，当前\[left, right\]不是回文子串，向外扩的也不可能是。外扩的方式就是使left–, right++。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]

**时间复杂度：O(N2) 空间复杂度：O(1)**

public int countSubstrings3(String s) { 
            char[] chars = s.toCharArray();
            int result = 0;
            for (int i = 0; i < chars.length * 2 - 1; i++) {  // 对每个可能的回文中心进行循环
                int left = i / 2; // 当中心是两个字母的间歇时i%2 = 1；当中心是字母时 left==right都落在该字母的位置
                int right = left + i % 2;
                while(left >= 0 && right < chars.length && chars[left] == chars[right]){ 
                    left--;
                    right++;
                    result++;
                }
            }
            return result;
        }

###### 3. 动态规划 ######

动态规划流程  
第 1 步：设计状态  
dp\[i\]\[j\] i开始j结尾的是否为回文字符串  
第 2 步：状态转移方程

for(int i = s.length()-1; i>=0; i--){ 
        for(int j = i+1; j<s.length(); j++){ 
            if(s.charAt(i) == s.charAt(j)){ 
                //i和j相邻的时候
                if(j - i == 1){ 
                    dp[i][j] = true;
                }
                else{ 
                    dp[i][j] = dp[i+1][j-1]
                }
            }
            else{ 
                dp[i][j] = false;
            }
        }
    }

第 3 步：考虑初始化  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]

第 4 步：考虑输出  
**统计 dp\[i\]\[j\] = T 的个数**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 3]

**时间复杂度：O(N) 空间复杂度：O(1)**

class Solution { 
        public int countSubstrings(String s) { 
            if(s == null || s.equals("")){ 
                return 0;
            }
            int n = s.length();
            boolean[][] dp = new boolean[n][n];
            int result = s.length();
            for(int i = 0; i<n; i++) dp[i][i] = true;
            for(int i = n-1; i>=0; i--){ 
                for(int j = i+1; j<n; j++){ 
                    if(s.charAt(i) == s.charAt(j)) { 
                     //i和j相邻的时候
                        if(j-i == 1){ 
                            dp[i][j] = true;
                        }
                        else{ 
                            dp[i][j] = dp[i+1][j-1]; 
                        }
                    }else{ 
                        dp[i][j] = false;
                    }
                    if(dp[i][j]){ 
                        result++;
                    }
                }
            }
            return result;
            
        }
    }

###### 2. Manacher 算法 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 4]

**时间复杂度：O(N) 空间复杂度：O(1)**

class Solution { 
        public int countSubstrings(String s) { 
            int n = s.length();
            StringBuffer t = new StringBuffer("$#");
            for (int i = 0; i < n; ++i) { 
                t.append(s.charAt(i));
                t.append('#');
            }
            n = t.length();
            t.append('!');
    
            int[] f = new int[n];
            int iMax = 0, rMax = 0, ans = 0;
            for (int i = 1; i < n; ++i) { 
                // 初始化 f[i]
                f[i] = i <= rMax ? Math.min(rMax - i + 1, f[2 * iMax - i]) : 1;
                // 中心拓展
                while (t.charAt(i + f[i]) == t.charAt(i - f[i])) { 
                    ++f[i];
                }
                // 动态维护 iMax 和 rMax
                if (i + f[i] - 1 > rMax) { 
                    iMax = i;
                    rMax = i + f[i] - 1;
                }
                // 统计答案, 当前贡献为 (f[i] - 1) / 2 上取整
                ans += f[i] / 2;
            }
    
            return ans;
        }
    }

#### 【总结】 ####

###### 1. 动态规划流程 ######

第 1 步：设计状态  
第 2 步：状态转移方程  
第 3 步：考虑初始化  
第 4 步：考虑输出  
第 5 步：考虑是否可以状态压缩

###### 2.暂时没有掌握 Manacher 算法（马拉车） ######

2.1 加\# 变奇数长度 收尾加标识  
2.2 初始化 中心扩展

###### 3. 想好再下手 思考得多敲得少 边敲边想反而会耗费更多的时间 ######

参考链接：https://leetcode-cn.com/problems/palindromic-substrings/solution/647java-bao-li-dpzhong-xin-kuo-zhan-xiang-jie-by-u/  
参考链接：链接：https://leetcode-cn.com/problems/palindromic-substrings/solution/647-hui-wen-zi-chuan-dong-tai-gui-hua-fang-shi-qiu/  
参考链接：https://leetcode-cn.com/problems/palindromic-substrings/solution/hui-wen-zi-chuan-by-leetcode-solution/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/be37b425336c451bafb6903e9a6b210b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221124/52fab739dc5d4b70b81c5015813ffe1a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221124/18aa9be7fed044b983769ca36c390db6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221124/6c20f1a4c73941608dc528f014ec771e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221124/65f271cda7ff4b81897731ee95578409.png