647. 回文子串

题目：

647. 回文子串

题解：

5. 最长回文子串

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

1. 解释一：
   
2. 解释二：
   
   
3. 解释三：
   

2. 题解二：动态规划

1. 解释一：
   
2. 解释二：
   
   
   
   

代码：

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