邢台市建设局网站,揭阳网站建设网站,福建高能建设工程有限公司网站,深圳电商网站制作公司LeetCode:647. 回文子串
647. 回文子串 - 力扣#xff08;LeetCode#xff09;
1.思路
暴力思路见对应代码…
动规解法#xff1a;画图推导动规公式#xff0c;当前状态由左侧和左下角推出#xff0c;所以首层应该采用倒序的方式#xff0c;内部采用正序的方式。
2.…LeetCode:647. 回文子串
647. 回文子串 - 力扣LeetCode
1.思路
暴力思路见对应代码…
动规解法画图推导动规公式当前状态由左侧和左下角推出所以首层应该采用倒序的方式内部采用正序的方式。
2.代码实现
// 暴力解法
// 思路两次for循环一层定起始位置一层定结束位置对每个连续的子串进行遍历判断定义区间判断子串是否为回文串的方法。
class Solution {public int countSubstrings(String s) {int count 0;for (int i 0; i s.length(); i) { // 定子串开始位置for (int j i; j s.length(); j) { // 定子串结束位置if (isValid(s, i, j)) { count; // 符合条件进行}}}return count;}// 判断是否为回文串private boolean isValid(String s, int start, int end) {while (start end) {if (s.charAt(start) ! s.charAt(end)) {return false;}start;end--;}return true;}
}// 动规思路在暴力解法的基础上对是否为回文串进行动态判断
class Solution {public int countSubstrings(String s) {char[] ch s.toCharArray();int len ch.length;boolean[][] dp new boolean[len][len];int result 0;for (int i len - 1; i 0; i--) {for (int j i; j 0; j--) {if (ch[i] ch[j]) {if (j - i 1) { // 表示同一个字符 或 相邻字符result;dp[i][j] true;} else if (dp[i 1][j - 1]) { //间隔大于1时判断内侧字符是否为回文串result;dp[i][j] true;}} }}return result;}
}3.复杂度分析
时间复杂度O(n^2). 空间复杂度O(n^2).定义dp数组
LeetCode:516.最长回文子序列
516. 最长回文子序列 - 力扣LeetCode
1.思路
最长回文子序列不一定连续。方格倒退一下可以获取遍历顺序为倒序内部为正序。每个字符均为1,也即dp[i][i] 1
2.代码实现
class Solution {public int longestPalindromeSubseq(String s) {int len s.length();int[][] dp new int[len 1][len 1];for (int i len - 1; i 0; i--) {dp[i][i] 1;for (int j i 1; j len; j) { // 倒序遍历if (s.charAt(i) s.charAt(j)) {dp[i][j] dp[i 1][j - 1] 2;} else {dp[i][j] Math.max(dp[i 1][j], Math.max(dp[i][j], dp[i][j - 1]));}}}return dp[0][len - 1];}
}3.复杂度分析
时间复杂度O(n^2). 空间复杂度O(n^2).
