You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
class Solution {
private int subSum = 0;
public int countSubstrings(String s) {
int i = 0;
for (i = 0; i < s.length(); ++i) {
countSub(s, i, i);
countSub(s, i, i + 1);
}
return subSum;
}
public void countSub(String s, int left, int right) {
while (left >= 0 && right < s.length()
&& s.charAt(left--) == s.charAt(right++))
++subSum;
}
}
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:
Example 2:
Note:
这道题跟**找出最长回文子字符串(5. Longest Palindromic Substring)**一样的思路。
首先直接用从中间字符遍历来判断,分为子字符串长度为奇数和偶数两种情况:
第二种就是DP的思路,声明一个dp二维数组,dp[i][j]表示子字符串i位置到j位置是否是回文,是为1,同时算入结果中,否为0。一开始要声明数组对角位置为1,表示单个字符串肯定是回文的。
一开始不知道如何使用DP,可以有这样一种思路:先考虑之间的DP关系,然后定义DP数组。比如这道题,如何判断[j...i]字符之间的substring是不是回文,就要判断[j+1...i-1]的字符串,如何可以定义二维DP数组。
怎么感觉这才是正常思路类似题目:
参考资料:
The text was updated successfully, but these errors were encountered: