647. 回文子串

红太狼 2022-12-02 12:20 204阅读 0赞

# 题目： #

[647. 回文子串][647.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center]

# 题解： #

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

## 1. 题解一：中心扩展算法 ##

1.  解释一：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 1]
2.  解释二：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 2]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 3]
3.  解释三：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 4]

## 2. 题解二：动态规划 ##

1.  解释一：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 5]
2.  解释二：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 6]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 7]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 8]  
    ![在这里插入图片描述][2020083019320544.png_pic_center]

# 代码： #

## 1. 代码一：中心扩展算法 ##

public class code647 { 
    
        // 解法1: 中心扩展算法
        public int num = 0;
    
        public int countSubstrings(String s) 
        { 
            for(int i = 0; i < s.length(); i++)
            { 
                count(s, i, i);     //回文串长度为奇数
                count(s, i, i + 1); //回文串长度为偶数
            }
            return num;
        }
    
        public void count(String s, int start, int end)
        { 
            while(start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end))
            { 
                num++;
                start--;
                end++;
            }
        }
    
        public static void main(String[] args) { 
    
            code647 test1 = new code647();
            String s1 = "abc";
            int res1 = test1.countSubstrings(s1);
            System.out.println(res1);
    
            code647 test2 = new code647();
            String s2 = "aaa";
            int res2 = test2.countSubstrings(s2);
            System.out.println(res2);
        }    
    }

## 2. 代码二：动态规划 ##

public class code647 { 
    
        // 解法2: 动态规划
        public int countSubstrings(String s) 
        { 
            int len = s.length();
            // dp[i][j] 表示字符串 s 在 [i, j] 区间的子串是否是一个回文串。
            boolean dp[][] = new boolean[len][len];
    
            int count = 0;
    
            for(int j = 0; j < len; j++)
            { 
                for(int i = 0; i <= j; i++)
                { 
                    // 当 (s.charAt(i) == s.charAt(j) 时，当元素个数为 1, 2, 3 ... n 个时，一定为回文子串
                    if(s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1]))
                    { 
                        dp[i][j] = true;
                        count++;
                    }
                }
            }
            return count;
        }
    
        public static void main(String[] args) { 
    
            code647 test1 = new code647();
            String s1 = "abc";
            int res1 = test1.countSubstrings(s1);
            System.out.println(res1);
    
            code647 test2 = new code647();
            String s2 = "aaa";
            int res2 = test2.countSubstrings(s2);
            System.out.println(res2);
        }    
    }

# 参考： #

1.  [回文子串][Link 1]
2.  [两道回文子串的解法（详解中心扩展法）][Link 2]
3.  [「手画图解」动态规划思路，以及降维优化][Link 3]
4.  [Manacher 只会求最长回文子串？太浪费了！][Manacher]
5.  [暴力法的优化-中心扩展法][-]
6.  [C++ 中规中矩的4ms解法（中心扩展 时间O(N^2)）][C_ _4ms_ _O_N_2]
7.  [【回文子串】中心扩散检查][Link 4]
8.  [Manacher算法图解][Manacher 1]
9.  [【Java】中心扩展法 简单快速 解决 回文子串问题！][Java_ _ _]
10. [647. 回文子串 动态规划方式求解][647. _]

[647.]: https://leetcode-cn.com/problems/palindromic-substrings/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/de1fbb757e9b42caaeebf67972d4e6f9.png
[5.]: https://blog.csdn.net/zyx_ly/article/details/90201691
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/311e76f176924dd1ba30aff3dfcca1ea.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/047ea6617c244d689a60f1ab7383544f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/013fae73f3234d99a8a85f1209f17d77.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/f62a71a3b9ba404cb3169ee0ec37f5ec.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/764f0296ea844290a18f2ce2d8d707ce.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221123/e1fa3583c1594254a091a9e6c9a289c3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221123/856731bb5f7643698f72398e117618a5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221123/eafb967fd9e04dae8663251a6a477e7e.png
[2020083019320544.png_pic_center]: /images/20221123/ced60e989a3a4d2aa9678dfc01a85a1d.png
[Link 1]: https://leetcode-cn.com/problems/palindromic-substrings/solution/hui-wen-zi-chuan-by-leetcode-solution/
[Link 2]: https://leetcode-cn.com/problems/palindromic-substrings/solution/liang-dao-hui-wen-zi-chuan-de-jie-fa-xiang-jie-zho/
[Link 3]: https://leetcode-cn.com/problems/palindromic-substrings/solution/shou-hua-tu-jie-dong-tai-gui-hua-si-lu-by-hyj8/
[Manacher]: https://leetcode-cn.com/problems/palindromic-substrings/solution/manacher-zhi-hui-qiu-zui-chang-hui-wen-zi-chuan-ta/
[-]: https://leetcode-cn.com/problems/palindromic-substrings/solution/jian-dan-de-dong-tai-gui-hua-si-xiang-by-tinylife/
[C_ _4ms_ _O_N_2]: https://leetcode-cn.com/problems/palindromic-substrings/solution/c-zhong-gui-zhong-ju-de-4msjie-fa-zhong-xin-kuo-zh/
[Link 4]: https://leetcode-cn.com/problems/palindromic-substrings/solution/palindromic-substrings-by-ikaruga/
[Manacher 1]: https://leetcode-cn.com/problems/palindromic-substrings/solution/manachersuan-fa-tu-jie-by-charming-ishi2aka/
[Java_ _ _]: https://leetcode-cn.com/problems/palindromic-substrings/solution/java-zhong-xin-kuo-zhan-fa-jian-dan-kuai-su-jie-ju/
[647. _]: https://leetcode-cn.com/problems/palindromic-substrings/solution/647-hui-wen-zi-chuan-dong-tai-gui-hua-fang-shi-qiu/