9. 验证是否为回文数字
Example 1:
Input: 121
Output: true
Example 2:
Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.
class Solution {
public:
bool isPalindrome(int x) {
if (x < 0) return false;
int div = 1;
while (x / div >= 10) div *= 10;
while (x > 0) {
int left = x / div;
int right = x % 10;
if (left != right) return false;
x = (x % div) / 10;
div /= 100;
}
return true;
}
};
5. 最长回文子串长度(内涵 子串是否为回文子串的dp递归)
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
时间复杂度： O(n^2) 两个for循环
空间复杂度： O(n^2) dp数组的大小
class Solution {
public String longestPalindrome(String s) {
int len = s.length();
// 特判
if (len < 2){
return s;
}
int maxLen = 1;
int begin = 0;
// 1. 状态定义
// dp[i][j] 表示s[i...j] 是否是回文串
// 2. 初始化
boolean[][] dp = new boolean[len][len];
for (int i = 0; i < len; i++) {
dp[i][i] = true;
}
char[] chars = s.toCharArray();
// 3. 状态转移
// 注意：先填左下角
// 填表规则：先一列一列的填写，再一行一行的填，保证左下方的单元格先进行计算
for (int j = 1;j < len;j++){
for (int i = 0; i < j; i++) {
// 头尾字符不相等，不是回文串
if (chars[i] != chars[j]){
dp[i][j] = false;
}else {
// 相等的情况下
// 考虑头尾去掉以后没有字符剩余，或者剩下一个字符的时候，肯定是回文串
if (j - i < 3){
dp[i][j] = true;
}else {
// 状态转移
dp[i][j] = dp[i + 1][j - 1];
}
}
// 只要dp[i][j] == true 成立，表示s[i...j] 是否是回文串
// 此时更新记录回文长度和起始位置
if (dp[i][j] && j - i + 1 > maxLen){
maxLen = j - i + 1;
begin = i;
}
}
}
// 4. 返回值
return s.substring(begin,begin + maxLen);
}
131. 分割回文串
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
思路：动态规划得到每个子串是否为回文子串，然后从头开始回溯算法
时间复杂度：O(N * 2^N)
public class Solution {
public List<List<String>> partition(String s) {
int len = s.length();
List<List<String>> res = new ArrayList<>();
if (len == 0) {
return res;
}
char[] charArray = s.toCharArray();
// 预处理
// 状态：dp[i][j] 表示 s[i][j] 是否是回文
boolean[][] dp = new boolean[len][len];
// 状态转移方程：在 s[i] == s[j] 的时候，dp[i][j] 参考 dp[i + 1][j - 1]
for (int right = 0; right < len; right++) {
// 注意：left <= right 取等号表示 1 个字符的时候也需要判断
for (int left = 0; left <= right; left++) {
if (charArray[left] == charArray[right] && (right - left <= 2 || dp[left + 1][right - 1])) {
dp[left][right] = true;
}
}
}
Deque<String> stack = new ArrayDeque<>();
dfs(s, 0, len, dp, stack, res);
return res;
}
private void dfs(String s, int index, int len, boolean[][] dp, Deque<String> path, List<List<String>> res) {
if (index == len) {
res.add(new ArrayList<>(path));
return;
}
for (int i = index; i < len; i++) {
if (dp[index][i]) {
path.addLast(s.substring(index, i + 1));
dfs(s, i + 1, len, dp, path, res);
path.removeLast();
}
}
}
}
132. 最小分割子串
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。
返回符合要求的 最少分割次数 。
示例 1：
输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
思路：
截屏2021-11-30 下午8.51.05.png
时间复杂度=空间复杂度=O(n^2)
class Solution {
public int minCut(String s) {
int n = s.length();
char[] cs = s.toCharArray();
// g[l][r] 代表 [l,r] 这一段是否为回文串
boolean[][] g = new boolean[n + 1][n + 1];
for (int r = 1; r <= n; r++) {
for (int l = r; l >= 1; l--) {
// 如果只有一个字符，则[l,r]属于回文
if (l == r) {
g[l][r] = true;
} else {
// 在 l 和 r 字符相同的前提下
if (cs[l - 1] == cs[r - 1]) {
// 如果 l 和 r 长度只有 2；或者 [l+1,r-1] 这一段满足回文，则[l,r]属于回文
if (r - l == 1 || g[l + 1][r - 1]) {
g[l][r] = true;
}
}
}
}
}
// f[r] 代表将 [1,r] 这一段分割成若干回文子串所需要的最小分割次数
int[] f = new int[n + 1];
for (int r = 1; r <= n; r++) {
// 如果 [1,r] 满足回文，不需要分割
if (g[1][r]) {
f[r] = 0;
} else {
// 先设定一个最大分割次数（r 个字符最多消耗 r - 1 次分割）
f[r] = r - 1;
// 在所有符合 [l,r] 回文的方案中取最小值
for (int l = 1; l <= r; l++) {
if (g[l][r]) f[r] = Math.min(f[r], f[l - 1] + 1);
}
}
}
return f[n];
}
}
647. 计数：回文子串数量
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"
class Solution {
public int countSubstrings(String s) {
// 动态规划法
boolean[][] dp = new boolean[s.length()][s.length()];
int ans = 0;
for (int j = 0; j < s.length(); j++) {
for (int i = 0; i <= j; i++) {
if (s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1])) {
dp[i][j] = true;
ans++;
}
}
}
return ans;
}
}
最长回文子序列
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。
class Solution {
public int longestPalindromeSubseq(String s) {
int n = s.length();
char[] cs = s.toCharArray();
int[][] f = new int[n][n];
for (int len = 1; len <= n; len++) {
for (int l = 0; l + len - 1 < n; l++) {
int r = l + len - 1;
if (len == 1) {
f[l][r] = 1;
} else if (len == 2) {
f[l][r] = cs[l] == cs[r] ? 2 : 1;
} else {
f[l][r] = Math.max(f[l + 1][r], f[l][r - 1]);
f[l][r] = Math.max(f[l][r], f[l + 1][r - 1] + (cs[l] == cs[r] ? 2 : 0));
}
}
}
return f[0][n - 1];
}
}
730. 统计不同回文子序列的个数
给定一个字符串 S，找出 S 中不同的非空回文子序列个数，并返回该数字与 10^9 + 7 的模。
通过从 S 中删除 0 个或多个字符来获得子序列。
如果一个字符序列与它反转后的字符序列一致，那么它是回文字符序列。
如果对于某个 i，A_i != B_i，那么 A_1, A_2, ... 和 B_1, B_2, ... 这两个字符序列是不同的。
示例 1：
输入：
S = 'bccb'
输出：6
解释：
6 个不同的非空回文子字符序列分别为：'b', 'c', 'bb', 'cc', 'bcb', 'bccb'。
注意：'bcb' 虽然出现两次但仅计数一次。
截屏2021-11-30 下午9.48.22.png
class Solution {
public int countPalindromicSubsequences(String s) {
int len = s.length();
int mod = (int) (1e9+7);
int dp[][] = new int[len][len];
for (int i = 0; i < len; i++) {
dp[i][i] = 1;
}
for (int i = len-2; i >= 0; i--) {
for (int j = i+1; j < len; j++) {
if(s.charAt(i) != s.charAt(j))
dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1];
else{
// +2 是因为两边的两个元素可以成为两个不重复的子序列
dp[i][j] = dp[i+1][j-1] *2 + 2;
//去掉重复的子序列
int l=i+1,r=j-1;
while(l<=r && s.charAt(l)!=s.charAt(i))
l++;
while(l<=r && s.charAt(r)!=s.charAt(i))
r--;
// 第2.1种情况 中间有1个s[i]
if(l == r)
dp[i][j]--;
// 第2.2种情况 中间有≥2个s[i]
else if(l < r)
dp[i][j] -=2+dp[l+1][r-1];
}
dp[i][j] = (dp[i][j]>=0) ? dp[i][j] % mod : dp[i][j]+mod;
}
}
return dp[0][len-1];
}
}
网友评论