• ㊗️
• 大家
• offer
• 多多！

Problem

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.

Code

class Solution {
int count = 0;

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

return count;
}

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

class Solution {
public int countSubstrings(String s) {
boolean[][] dp = new boolean[s.length()][s.length()];
int res = 0;

for (int len = 1; len <= s.length(); len++) {
for (int i = 0; i <= s.length() - len; i++) {
int j = i + len - 1;
if (s.charAt(i) == s.charAt(j)) {
if (j - i <= 2 || dp[i + 1][j - 1]) {
dp[i][j] = true;
res++;
}
}

}
}

return res;
}
}