647 Palindromic Substrings

647-Palindromic Substrings

题目：Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Example 1: Input: “abc” Output: 3 Explanation: Three palindromic strings: “a”, “b”, “c”.

Example 2: Input: “aaa” Output: 6 Explanation: Six palindromic strings: “a”, “a”, “a”, “aa”, “aa”, “aaa”.

题目本身还是比较容易理解的，求一个字符串的回文子串的个数，这里一个单独的字符算回文。我其实知道最直接的思路肯定是不符合时间复杂度要求的，但还是可以写一下，对每一个子串(substring)，判断其是否是回文，是就加一。

方法一：

public int countSubstrings(String s) {
    int count = 0;
    int len = s.length();
    for (int i = 0; i < len; i++) {
        for (int j = i; j < len; j++) {
            if (judge(s, i, j)) {
                count++;
            }
        }
    }
    return count;
}

private boolean judge(String s, int start, int end) {
    while (start < end) {
        if (s.charAt(start++) != s.charAt(end--)) {
            return false;
        }
    }
    return true;
}

注意这个最基本解法的时间复杂度是O(n^3)，两次for循环求子串，一次循环判断这个串是否回文，值得注意的也就是判断一个字符串是否回文的smart写法——s.charAt(start++) != s.charAt(end–)。

提交这个解法的结果是：可以看到耗时太长

执行耗时:114 ms,击败了8.26% 的Java用户内存消耗:34.3 MB,击败了100.00% 的Java用户

方法二：看了一些解答后，可以利用回文串的一个特性，即当在回文串两端各加入两个相同的字符的时候，形成的新字符仍旧是回文串。注意一下，回文串可以是一个单个的字符，也可以是两个字符，划分奇偶性。用递归的方式，遍历字符串，以字符串的每一个字符当作回文串的中间位置，然后依次向两边扩展，若两个字符相等，count加一，然后各自向两边扩展，比较下一对。本质上是一个双指针，从中间向两边移动。需要注意的就是回文串的中间位置可能是一个字符(如aba)，则中间位置是b；也可能是一个位置(如aa)，则中间位置是两个a之间的的位置。因此本质上遍历字符串的时候，我们是以当前字符串或者 当前字符串旁边的位置为回文串的中间位置，来做加法的。

public int countSubstrings(String s) {
    int count = 0;
    for (int i = 0; i < s.length(); i++) {
        count += count(s, i, i);
        count += count(s, i, i + 1);
    }
    return count;
}

private int count(String s, int left, int right) {
    int result = 0;
    while (left >= 0 && right < s.length() && s.charAt(left--) == s.charAt(right++)) {
        result++;
    }
    return result;
}

这个双指针法也是网上比较通用的一种方法，主要利用的是回文串的特性，来做到O(n^2)的时间复杂度，但是这道题求的是回文子串的个数，其实是可以有相同的。

解法二的执行结果：

执行耗时:1 ms,击败了99.97% 的Java用户内存消耗:34.2 MB,击败了100.00% 的Java用户

方法三：有很多人也使用了动态规划的思想来做这道题，即使整体上不如双指针法高效：使用dp[i][j]来定义字符串[i, j]是否是回文。 i从n-1开始，j从i开始到n，这里需要思考为什么是这样的遍历顺序，看s[i]是否等于s[j]。这个时候需要留意的就是i和j的位置关系了：

如果i == j，则dp[i][j]肯定是true；
如果i和j相邻，则dp[i][j]还是true；
如果i和j中间相隔一个字符，则dp[i][j]还是true；
如果i和j中间的字符多于一个，则dp[i][j]就取决于dp[i + 1][j - 1]的值了

public int countSubstrings(String s) { int count = 0; int len = s.length(); boolean [][] dp = new boolean[len][len]; for (int i = len - 1; i >= 0; i–) { for (int j = i; j < len; j++) { dp[i][j] = (s.charAt(i) == s.charAt(j)) && (j - i <= 2 || dp[i + 1][j - 1]); if (dp[i][j]) { count++; } } } return count; } 方法三的执行结果：并不如双指针来得高效。

执行耗时:6 ms,击败了37.80% 的Java用户内存消耗:35.9 MB,击败了50.63% 的Java用户