一. 回文子串
回文子串
- 状态表示
将所有子串是否是回文串的信息, 保存在dp表中
dp[i][j] 表示 从i到j的子串是否是回文串 - 状态转移方程
如果s[i] != s[j] 一定不是回文子串
如果s[i] == s[j] 分三种情况:
1.i == j 指同一个字符, 一定是回文串 true
2.i + 1 == j 两个字符, 一定是回文串 true
3.dp[i][j] = dp[i + 1][j - 1] - 初始化
无需初始化 上面的条件已经帮我们完成 - 填表顺序
从下往上, 从左往右 - 返回值
返回true的个数
class Solution {public int countSubstrings(String s) {int n = s.length();char[] ss = s.toCharArray();boolean[][] dp = new boolean[n][n];int ret = 0;for (int i = n - 1; i >= 0; i--) {for (int j = i; j < n; j++) {if (ss[i] == ss[j]) {if (i == j) {dp[i][j] = true;} else if (i + 1 == j) {dp[i][j] = true;} else {dp[i][j] = dp[i + 1][j - 1];}}if (dp[i][j]) {ret++;}}}return ret;}
}
二. 最长回文子串
最长回文子串
class Solution {public String longestPalindrome(String s) {int n = s.length();boolean[][] dp = new boolean[n][n];int p = 0, len = 0;for(int i = n; i >= 0; i--){for(int j = i; j < n; j++){if(s.charAt(i) == s.charAt(j)){if(i == j || i + 1 == j) dp[i][j] = true;else dp[i][j] = dp[i + 1][j - 1]; }if(dp[i][j] && j - i + 1 > len){p = i; len = j - i + 1;}}}return s.substring(p, p + len);}
}
三. 回文串分割IV
回文串分割
用i j 表示中间子串的开始和结束位置
字符串被分成dp[0][i - 1] && dp[i][j] && dp[j + 1][n - 1] 三部分
class Solution {public boolean checkPartitioning(String s) {int n = s.length();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 == j || i + 1 == j) dp[i][j] = true;else dp[i][j] = dp[i + 1][j - 1];}}}for(int i = 1; i < n - 1; i++){for(int j = i; j < n - 1; j++){if(dp[0][i - 1] && dp[i][j] && dp[j + 1][n - 1]) return true;}}return false;}
}
四. 分割回文串II
- 状态表示
dp[i][j] 表示 (0, i)字符串中, 需要分割的最小次数 - 状态转移方程
1.(0, i)是回文串, dp[i] = 0;
2.(0, i)不是回文串, 分成两种情况
定义j, 0 < j <= i
如果(j, i)是回文串, dp[i] = dp[i - 1] + 1
如果(j, i)不是回文串, 判断下一个位置
- dp[i] = min(dp[i - 1] + 1)
- 初始化
dp每个元素初始化为最大值, 防止干扰结果 - 填表顺序
从左往右 - 返回值
dp[n - 1]
class Solution {public int minCut(String s) {int n = s.length();boolean[][] tmp = new boolean[n][n];int[] dp = new int[n];Arrays.fill(dp, Integer.MAX_VALUE);for (int i = n - 1; i >= 0; i--) {for (int j = i; j < n; j++) {if (s.charAt(i) == s.charAt(j)) {if (i == j || i + 1 == j)tmp[i][j] = true;elsetmp[i][j] = tmp[i + 1][j - 1];}}}for (int i = 0; i < n; i++) {if (tmp[0][i])dp[i] = 0;else {for (int j = 1; j <= i; j++) {if (tmp[j][i])dp[i] = Math.min(dp[j - 1] + 1, dp[i]);}}}return dp[n - 1];}
}五. 最长回文子序列
最长回文子序列
-
状态表示
dp[i][j] 表示 (i, j)字符串中, 最长回文子序列 -
状态转移方程
如果s[i] == s[j] :
1.i == j , 最长为1
2.i +1 = j, 最长为2
3.其余情况, 要找i + 1 和 j - 1 的最长回文子序列 + 2
如果s[i] != s[j] : 说明不是ij都选, 只选择其中一个, 求最大值
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) -
初始化
无需初始化, 不会越界 -
填表顺序
从左往右, 从下往上 -
返回值
dp[0][n - 1]
class Solution {public int longestPalindromeSubseq(String s) {int n = s.length();int[][] dp = new int[n][n];for (int i = n - 1; i >= 0; i--) {dp[i][i] = 1;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];}
}
六. 让字符串成为回文串的最少插入次数
让字符串成为回文串的最少插入次数
- 状态表示
dp[i][j] 表示 (i, j)字符串中, 让字符串成为回文串的最少插入次数 - 状态转移方程
如果s[i] == s[j] :
1.i == j , 最少次数为0
2.i +1 = j, 最少次数为0
3.其余情况, 要找i + 1 和 j - 1 的最少次数, 为dp[i + 1][j - 1]
如果s[i] != s[j]
可以在 i 之前插入s[j], dp[i][j] = dp[i][j - 1] + 1
可以在 j 之后插入s[i], dp[i][j] = dp[i + 1][j] + 1
- dp[i][j] = min(dp[i][j - 1] + 1, dp[i + 1][j] + 1)
- 初始化
无需初始化, 不会越界 - 填表顺序
从左往右, 从下往上 - 返回值
dp[0][n - 1]
class Solution {public int minInsertions(String s) {int n = s.length();int[][] dp = new int[n][n];for (int i = n - 1; i >= 0; i--) {for (int j = i + 1; j < n; j++) {if (s.charAt(i) == s.charAt(j)) {if (i + 1 < j) {dp[i][j] = dp[i + 1][j - 1];}} else {dp[i][j] = Math.min(dp[i][j - 1], dp[i + 1][j]) + 1;}}}return dp[0][n - 1];}
}
