草稿圖網站
java的Deque

Leetcode 647. 回文子串

題目：647. 回文子串
解析：代碼隨想錄解析

解題思路

斜上三角，從左下往上遍歷，如果當前的兩端的字符相等，長度為1或2，則為true，res++；如果超過2，則根據內部是否為true來決定是否設為true，res++

代碼

class Solution {public int countSubstrings(String s) {int n = s.length();int res = 0;boolean [][]dp = new boolean[n][n];for (int i = n-1; i >= 0; i--) {for (int j = i; j < n; j++) {if (s.charAt(i) == s.charAt(j)) {if (i + 1 >= j) { // i,i 活 i,i+1dp[i][j] = true;res++;} else if (dp[i+1][j-1]) {dp[i][j] = true;res++;}}}}return res;}
}

總結

暫無

Leetcode 516. 最長回文子序列

題目：516. 最長回文子序列
解析：代碼隨想錄解析

解題思路

dp數組的含義是i到j的子串中回文子串最長的是多少。

代碼

class Solution {public int longestPalindromeSubseq(String s) {int n = s.length();int [][]dp = new int[n][n];//i到j的子串中回文子串最長的是多少for (int i = 0; i < n; i++)dp[i][i] = 1;for (int i = n - 1; i >= 0; i--) {for (int j = i + 1; j < n; 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], dp[i][j-1]);}}}return dp[0][n-1];}
}

總結

暫無