[LeetCode] 647. 回文子串 ☆☆☆(最长子串、动态规划、中心扩展算法)
2023-09-14 09:07:34 时间
描述
给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被计为是不同的子串。
示例 1:
输入: "abc"
输出: 3
解释: 三个回文子串: "a", "b", "c".
示例 2:
输入: "aaa"
输出: 6
说明: 6个回文子串: "a", "a", "a", "aa", "aa", "aaa".
注意:
输入的字符串长度不会超过1000。
解析
和[LeetCode] 5. 最长回文子串 ☆☆☆(最长子串、动态规划)类似,可以先考虑用中心扩展法,与其不同的是,记录回文子串个数。
也可以用动态规划。
思路为:
如果从i到j的字符串是回文字符串,那么如果i-1和j+1相等,那么从i-1到j+1就是回文字符串。
当然,如果是1个字符串,那么一定是回文的,如果是两个字符串,并且相等,那么也是回文的。
代码
中心扩展算法
public int countSubstrings(String s) { int count = 0; for (int i = 0; i < s.length(); i++) { count += count(s, i, i);//回文子串长度为奇数的情况 count += count(s, i, i + 1);//回文子串长度为偶数的情况 } return count; } public static int count(String s, int start, int end) { int count = 0; //start往左边跑,end往右边跑,注意边界 while (start >= 0 && end < s.length() && s.charAt(start--) == s.charAt(end++)) { count++; } return count; }
动态规划
public static int countSubstrings(String s) { int result = 0; boolean[][] dp = new boolean[s.length()][s.length()];//i到j位置的字符串是否为回文子串 for (int i = 0; i < s.length(); i++) { for (int j = 0; j <= i; j++) { if (i == j) { dp[i][j] = true;//i j相等,肯定是回文子串 } else {//i j不等的话,如果char一样,i j相差1,也符合;或者最近的内圈是回文子串 dp[i][j] = s.charAt(i) == s.charAt(j) && (j == i - 1 || dp[i - 1][j + 1]); } if (dp[i][j]) { result++; } } } // for (int i = s.length() - 1; i >= 0 ; i--) {//类似,只是从后往前 // for (int j = i; j < s.length(); j++) { // if (i == j) // dp[i][j] = true; // else // dp[i][j] = s.charAt(i) == s.charAt(j) && (j == i + 1 || dp[i + 1][j - 1]); // if (dp[i][j]) result++; // } // } return result; }
相关文章
- Java实现 LeetCode 887 鸡蛋掉落(动态规划,谷歌面试题,蓝桥杯真题)
- Java实现 LeetCode 714 买卖股票的最佳时机含手续费(动态规划 || 迭代法)
- Java实现 LeetCode 535 TinyURL 的加密与解密(位运算加密)
- Java实现 LeetCode 406 根据身高重建队列
- Java实现 LeetCode 103 二叉树的锯齿形层次遍历
- 每日一道 LeetCode (48):最长回文子串
- LeetCode-1234. 替换子串得到平衡字符串【滑动窗口,字符串】
- LeetCode-面试题 17.09. 第 k 个数【三指针,动态规划,最小堆】
- LeetCode-813. 最大平均值和的分组【动态规划,前缀和】
- LeetCode-828. 统计子串中的唯一字符【哈希表,字符串,动态规划】
- LeetCode-357. 统计各位数字都不同的数字个数【排列组合,递归,动态规划】
- Leetcode学习计划之动态规划入门day9(139,42)
- Leetcode学习计划之动态规划入门day6(152, 1567)
- Leetcode学习计划之动态规划入门day5(53,918)
- 【LeetCode Python实现】ZJ27 字典树
- [LeetCode] 139. 单词拆分 ☆☆☆(动态规划 回溯)
- [LeetCode] 120. 三角形最小路径和 ☆☆☆(动态规划 范例)
- [LeetCode] 63. 不同路径 II ☆☆☆(动态规划)
- [LeetCode] 72. 编辑距离 ☆☆☆☆☆(动态规划)
- [LeetCode] Search in Rotated Sorted Array II [36]
- 【Leetcode刷题Python】高效求递归中函数的调用次数(动态规划方法,顺丰笔试题)