网站建设公司市场策划方案,深圳网站建设黄浦网络 技术差,豆瓣wordpress主题,网站飘窗怎么做题目链接 剑指 Offer II 020. 回文子字符串的个数 mid 题目描述
给定一个字符串 s#xff0c;请计算这个字符串中有多少个回文子字符串。
具有不同开始位置或结束位置的子串#xff0c;即使是由相同的字符组成#xff0c;也会被视作不同的子串。
示例 1#xff1a; 输入…题目链接 剑指 Offer II 020. 回文子字符串的个数 mid 题目描述
给定一个字符串 s请计算这个字符串中有多少个回文子字符串。
具有不同开始位置或结束位置的子串即使是由相同的字符组成也会被视作不同的子串。
示例 1 输入s “abc” 输出3 解释三个回文子串: “a”, “b”, “c” 示例 2 输入s “aaa” 输出6 解释6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa” 提示
1s.length10001 s.length 10001s.length1000s由小写英文字母组成
分析
使用 动态规划 解决本题。
我们定义 f(i,j)f(i,j)f(i,j)为 s[i - 1,j - 1]区间是否为回文串。
当 s[i−1]≠s[j−1]s[i-1] \neq s[j-1]s[i−1]s[j−1]那么 f[i][j] false.当 s[i−1]s[j−1]s[i-1] s[j-1]s[i−1]s[j−1] 如果 j−i≤1j - i \leq1j−i≤1s[i][j] true相当于指针 i和 j指向了一个字符a或者指向了两个相连且相等的字符 aa。 如果 f[i-1][j1] trues[i][j] true。
时间复杂度 O(n2)O(n^2)O(n2)
C代码
class Solution {
public:int countSubstrings(string s) {int n s.size();bool f[n1][n1];memset(f,false,sizeof f);int ans 0;for(int i n;i 1;i--){for(int j i;j n;j){if((s[i-1] s[j - 1]) (j - i 1 || f[i1][j-1])){ans;f[i][j] true;}}}return ans;}
};
Java代码
class Solution {public int countSubstrings(String s) {int n s.length();boolean[][] f new boolean[n1][n1];int ans 0;for(int i n;i 1;i--){for(int j i;j n;j){if((s.charAt(i-1) s.charAt(j-1)) (j - i 1 || f[i1][j-1])){ans;f[i][j] true;}}}return ans;}
}
