leetcode

LeetCode 647. Palindromic Substrings

Problem

LeetCode 647. Palindromic Substrings

1. 题目简述

找出一个字符串的所有回文子字符串数量。例如：

Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

2. 算法思路

思路和LeetCode 5是一样的，都是找回文子字符串，只不过5是找最长的回文子字符串，这里是找所有回文子字符串的数量。

其实就是相当于每次找到回文字符串的时候count++就OK了，记得在dp[i][i]赋值的时候+1。

Dynamic Programming

和“LeetCode 5”是一样的解析，这里不多做解释了。

中心扩散法

这里同理，注意count++的时机。

3. 解法

Dynamic Programming bottom-up


public class Solution {
    public int countSubstrings(String s) {
        if (s.length() <= 1) {
            return s.length();
        }

        int n = s.length(), count = 0;
        boolean[][] dp = new boolean[n][n];

        for (int i = n - 1; i >= 0; i--) {
            dp[i][i] = true;
            count++;
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j) && ((j - i <= 2 )|| dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    count++;
                }
            }
        }

        return count;
    }
}

中心扩散法

public class Solution {
    public int countSubstrings(String s) {
        if (s.length() <= 1) {
            return s.length();
        }

        int n = s.length(), count = 0;
        for (int i = 0; i < n; i++) {
            count += findPalindrome(s, i, i) + findPalindrome(s, i , i+ 1);
        }

        return count;
    }

    private int findPalindrome(String s, int l, int r) {
        int count = 0;
        while (l >=0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            count++;
            l--;
            r++;
        }
        return count;
    }
}