[LeetCode] 647. Palindromic Substrings 回文子字符串
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:
Input: "abc" Output: 3 Explanation: Three palindromic strings: "a", "b", "c".
Example 2:
Input: "aaa" Output: 6 Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
Note:
- The input string length won't exceed 1000.
这道题给了一个字符串,让我们计算有多少个回文子字符串。博主看到这个题,下意识的想着应该是用 DP 来做,哼哼哧哧写了半天,修修补补,终于通过了,但是博主写的 DP 不是最简便的方法,略显复杂,这里就不贴了。还是直接讲解大神们的解法好了。其实这道题也可以用递归来做,而且思路非常的简单粗暴。就是以字符串中的每一个字符都当作回文串中间的位置,然后向两边扩散,每当成功匹配两个左右两个字符,结果 res 自增1,然后再比较下一对。注意回文字符串有奇数和偶数两种形式,如果是奇数长度,那么i位置就是中间那个字符的位置,所以左右两遍都从i开始遍历;如果是偶数长度的,那么i是最中间两个字符的左边那个,右边那个就是 i+1,这样就能 cover 所有的情况啦,而且都是不同的回文子字符串,参见代码如下:
解法一:
class Solution { public: int countSubstrings(string s) { if (s.empty()) return 0; int n = s.size(), res = 0; for (int i = 0; i < n; ++i) { helper(s, i, i, res); helper(s, i, i + 1, res); } return res; } void helper(string s, int i, int j, int& res) { while (i >= 0 && j < s.size() && s[i] == s[j]) { --i; ++j; ++res; } } };
在刚开始的时候博主提到了自己写的 DP 的方法比较复杂,为什么呢,因为博主的 dp[i][j] 定义的是范围 [i, j] 之间的子字符串的个数,这样其实还需要一个二维数组来记录子字符串 [i, j] 是否是回文串,那还不如直接就将 dp[i][j] 定义成子字符串 [i, j] 是否是回文串就行了,然后i从 n-1 往0遍历,j从i往 n-1 遍历,然后看 s[i] 和 s[j] 是否相等,这时候需要留意一下,有了 s[i] 和 s[j] 相等这个条件后,i和j的位置关系很重要,如果i和j相等了,则 dp[i][j] 肯定是 true;如果i和j是相邻的,那么 dp[i][j] 也是 true;如果i和j中间只有一个字符,那么 dp[i][j] 还是 true;如果中间有多余一个字符存在,则需要看 dp[i+1][j-1] 是否为 true,若为 true,那么 dp[i][j] 就是 true。赋值 dp[i][j] 后,如果其为 true,结果 res 自增1,参见代码如下:
解法二:
class Solution { public: int countSubstrings(string s) { int n = s.size(), res = 0; vector<vector<bool>> dp(n, vector<bool>(n)); for (int i = n - 1; i >= 0; --i) { for (int j = i; j < n; ++j) { dp[i][j] = (s[i] == s[j]) && (j - i <= 2 || dp[i + 1][j - 1]); if (dp[i][j]) ++res; } } return res; } };
Github 同步地址:
https://github.com/grandyang/leetcode/issues/647
类似题目:
Longest Palindromic Subsequence
参考资料:
https://leetcode.com/problems/palindromic-substrings/
相关文章
- Java实现 LeetCode 837 新21点(DP)
- Java实现 LeetCode 730 统计不同回文子字符串(动态规划)
- Java实现 LeetCode 730 统计不同回文子字符串(动态规划)
- Java实现 LeetCode 680 验证回文字符串 Ⅱ(暴力)
- Java实现 LeetCode 912 排序数组(用数组去代替排序O(N))
- Java实现 LeetCode 589 N叉树的前序遍历(遍历树)
- Java实现 LeetCode 517 超级洗衣机
- Java实现 LeetCode 495 提莫攻击
- Java实现 LeetCode 355 设计推特
- SQL Server实现 LeetCode 177 第N高的薪水
- Java实现 LeetCode 89 格雷编码
- 【贪心】LeetCode 11. 盛最多水的容器【中等】
- (LeetCode 160)Intersection of Two Linked Lists
- [LeetCode] Increasing Triplet Subsequence
- Leetcode.面试题 05.02 二进制数转字符串
- LeetCode-283. 移动零【数组,双指针】
- LeetCode-1704. 判断字符串的两半是否相似【计数,双指针】
- LeetCode-942. 增减字符串匹配【贪心,双指针,数学】
- 【克隆子串】+LeetCode-459. 重复的子字符串
- 【LeetCode Python实现】水仙花数
- 【LeetCode 中等 链表 python3】2. 两数相加
- Leetcode 680. 验证回文字符串 Ⅱ(可以,已解决)
- Leetcode 1974. 使用特殊打字机键入单词的最少时间(可以,一次过)
- Leetcode 1221. 分割平衡字符串
- Leetcode 796. 旋转字符串
- Leetcode 680. 验证回文字符串 Ⅱ(待解决)
- LeetCode 1662. 检查两个字符串数组是否相等
- 【LeetCode】剑指 Offer II 020. 回文子字符串的个数
- 【LeetCode】76. 最小覆盖子串
- leetcode 字符串转换整数 (atoi)