/**
Given a string s, return the number of palindromic substrings in it.
A string is a palindrome when it reads the same backward as forward.
A substring is a contiguous sequence of characters within the string.
Example 1:
Input: s = "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".
Example 2:
Input: s = "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
Constraints:
1 <= s.length <= 1000
s consists of lowercase English letters.
Related Topics字符串 | 动态规划
👍 1012, 👎 0
*/
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public int countSubstrings(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int[] dp = new int[s.length()];
dp[0] = 1;
Boolean[][] isP = new Boolean[s.length()][s.length()];
for (int i = 0; i < s.length(); i++) {
isP[i][i] = true;
}
for (int i = 1; i < s.length(); i++) {
int cnt = 0;
for (int j = 0; j <= i; j++) {
if (isPalindromic(s, isP, j, i)) {
cnt++;
}
}
dp[i] = dp[i - 1] + cnt;
}
return dp[s.length() - 1];
}
private boolean isPalindromic(String s, Boolean[][] isP, int from, int end) {
if (end < from) {
return true;
}
if (isP[from][end] != null) {
return isP[from][end];
}
if (s.charAt(from) == s.charAt(end) && isPalindromic(s, isP, from + 1, end - 1)) {
isP[from][end] = true;
return true;
} else {
isP[from][end] = false;
return false;
}
}
}
//leetcode submit region end(Prohibit modification and deletion)
