LeetCode_145_PalindromicSubstrings

1. question: 回文子串（中等）

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/palindromic-substrings

示例 1：

输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例 2：

输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示：

1 <= s.length <= 1000
s 由小写英文字母组成

2. answers

这道题最开始我自己以接近超时的方式做出来了。动态规划+双指针法判断回文串。

首先以首尾双指针法判断回文串，这没什么可说的，直接做就行。其次是动态规划，定义数组dp[i]表示字符串s[0:i]所能形成的回文串的数量，那么s[0:i+1]和前面有什么关系吗？答案是有的。

1. 字符串s[0:i+1]所能形成的回文串一定是s[0:i]和s[i+1]，以及s[x:i+1]所形成的回文串总和。
2. 其中s[0:i]所形成的回文串数量已经有前面得到，s[i+1]就是一个字符，显然回文串数量为1。
3. 那么s[x:i+1]实际上就是以s[i+1]为结尾的这i个字符串是否是回文串就行。

代码如下所示：

public class Solution_0145 {

    public boolean isSubstrings(String s) {
        // 保证s的长度至少为1
        // 双指针法判断是否是回文串
        int start = 0;
        int end = s.length() - 1;

        while(start <= end) {
            if(s.charAt(start) != s.charAt(end)) return false;

            start++;
            end--;
        }

        return true;
    }

    public int countSubstrings(String s) {

        int[] dp = new int[s.length()];

        dp[0] = 1;

        for (int i = 1; i < s.length(); i++) {

            dp[i] = dp[i-1] + 1;
            // 判断s[0:i]所形成的i个字符串，是否是回文串
            for (int j = 0; j < i; j++) {
                if(isSubstrings(s.substring(j, i + 1))) dp[i] += 1;
            }

        }

        return dp[s.length() - 1];
    }

    public static void main(String[] args) {

        Solution_0145 s0145 = new Solution_0145();

        String s = "aaa";

        System.out.println(s0145.countSubstrings(s));
    }
}

上面的时间复杂度接近O(n^3)，参考题解，可采用动态规划。代码如下所示：

/**
 *
 * 以完全动态规划的思路来看一下。
 *
 * 定义数组dp[i][j]表示s[i:j]子串是否是回文串，显然i<=j。注意[i:j]为闭区间。状态转移如下所示：
 *      1. 如果 i==j，即单个字符，此时一定是回文串
 *      2. 如果 j - i == 1，即两个字符。如果s[i] == s[j]，一定是回文串；否则不是回文串。
 *      3. 如果 j - i > 1，即超过了两个字符。
 *              1. 如果s[i] != s[j]，肯定不是回文串。
 *              2. 如果s[i] == s[j]，那么就取决于 s[i+1:j-1]是不是回文串。随即产生了递推关系。
 *
 *  那么怎么初始化呢？显然对角线上的都是true。其他的位置呢？先暂时设置为false
 *
 *  因为i一定是小于等于j的，所以应该是对对角线右上角部分进行遍历。并且在遍历的时候用到了左下角的值，因此，大方向应该是从左下到右上。
 */
public class Solution_0145_02 {

    public int countSubstrings(String s) {

        // 默认初始化为false
        boolean[][] dp = new boolean[s.length()][s.length()];
        int result = 0;

        // 对角线初始化为true
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < s.length(); j++) {
                if(i == j) {
                    dp[i][j] = true;
                    result++;
                }
            }
        }

        // 动态规划，注意遍历顺序，这里是每一行从左到右，逐行从下到上。
        // 因为对角线的缘故，所以从倒数第二行开始遍历
        for (int i = s.length() - 2; i >= 0 ; i--) {

            for (int j = i + 1; j < s.length(); j++) {

                // 只有相等，才可能是回文串
                if(s.charAt(i) == s.charAt(j)) {
                    if(j - i <= 1) {
                        dp[i][j] = true;
                        result++;
                    }
                    // 长度大于2，即j-i>=2，j>=i+2, j-1>=i+1，即仍然是对角线及其往上。所以没有超出边界。
                    else {
                        dp[i][j] = dp[i+1][j-1];
                        if(dp[i][j]) result++;
                    }
                }

            }
        }

        return result;
    }

    public static void main(String[] args) {
        System.out.println();

        Solution_0145_02 s0145_02 = new Solution_0145_02();

        String s = "aaa";

        System.out.println(s0145_02.countSubstrings(s));

    }
}

除了上面的动态规划，其实可以采用中心扩散双指针法。代码如下所示：

/**
 *
 * 参考题解，以中心扩散双指针法来做一下。
 *
 * 回文串要么是奇数个元素，要么是偶数个元素。那么从原始字符串的角度来看，显然，每个元素都可作为回文串的中心节点【以及偶数个节点】。
 *
 * 因此，可直接遍历，将节点作为中心节点，向两边扩散判断形成的子串是否是回文串即可。
 */
public class Solution_0145_03 {

    public boolean isSubstrings(String s) {
        // 保证s的长度至少为1
        // 双指针法判断是否是回文串
        int start = 0;
        int end = s.length() - 1;

        while(start <= end) {
            if(s.charAt(start) != s.charAt(end)) return false;

            start++;
            end--;
        }

        return true;
    }

    public int countSubstrings(String s) {

        if(s.length() == 1) return 1;

        int subRange = 0;
        int result = 0;

        for (int i = 0; i < s.length(); i++) {

            // 单个中心点
            // 计算本子串的1/2长度
            subRange = Math.min(i, s.length() - 1 - i);
            while(subRange >= 0) {
                if(isSubstrings(s.substring(i-subRange, i+subRange + 1))) result++;
                subRange--;
            }

            // 两个中心点，即当前节点以及下一个节点作为中心点
            // 计算本子串的1/2长度
            subRange = Math.min(i, s.length() - 1 - (i + 1));
            while(subRange >= 0) {
                if(isSubstrings(s.substring(i-subRange, (i+1)+subRange + 1))) result++;
                subRange--;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        System.out.println();
        Solution_0145_03 s0145 = new Solution_0145_03();

        String s = "ab";

        System.out.println(s0145.countSubstrings(s));
    }
}

3. 备注

参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。