目录
给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
示例 2：
提示：输入的字符串长度不会超过 1000 。
? ? ? ? ?按照回溯来做，没做出来，没法用回溯来写
? ? ? ? 使用暴力可以解
? ? ? ? 使用dp 将数目记录，但是递推公式不好计算? ? ?
????????
? ? ? ? 用动态规划，若i==j 则看i和j之间是否是回文串，如果是回文则dp[i][j]也是回文
? ? ? ? (选中两个单词的字符，若相同看中间是否是回文)
? ? ? ? 确定dp数组和每个下标的含义
? ? ? ? dp[i][j],看i和j之间是否是回文串
? ? ? ??
????????
? ? ? ? 确定递推公式
? ? ? ? ? ? ? ?若s[i]==s[j] 则有三种情况
? ? ? ? ? ? ? ? 若i==j 则dp[i][j]=true
? ? ? ? ? ? ? ? 若i=j-1 则dp[i][j]=true
? ? ? ? ? ? ? ? 若i>j-1，则dp[i][j] = dp[i+1][j-1]（看i，j中间的是否是回文串）
????????dp数组初始化
? ? ? ? 初始化都为false，相当于遍历时若为回文则改为true? ??
? ? ? ? 确定遍历顺序
? ? ? ? dp[i][j] 依赖于 dp[i+1][j-1] 则可以从下往上，从左往右进行遍历
? ? ? ? 举例推导dp数组? ? ? ? ? ?
? ? ? ? 打印dp数组
? ? ? ? 遍历时记录true的个数，返回总数，就是回文子串的个数了
? ? ? ? 回溯没写出来
? ? ? ? 第一时间想一下暴力
? ? ? ? 回文串记得通过[i,j]中间的来进行判断
????????
class Solution {
public int countSubstrings(String s) {
//我的思路是记录回文子串数目，其中dp数组是不太好推测的
//卡哥的思路是，利用dp[i][j]二维数组，看[i，j] 是否是回文子串
//若为回文子串则为true ，若不为则为false
//若 s[i] s[j]相等，那么我们可以看[i+1][j-1] 是否为回文子串,若为回文，则dp[i][j]也为回文(相当于包在里面)
//确定dp数组和下标的含义
// dp[i][j] 看[i,j]是否为回文子串，若是则为true，否则为false
//确定递推公式
// 若s[i]=s[j] 有三种情况 1 i==j 则直接为true
// 2 i==j-1 则直接为true
// 3 i<j-1 则需要判断 若dp[i+1][j-1]==true 则dp[i][j]为true
//dp数组初始化
//全都为false ，先默认都不为回文子串，然后再一个个改成回文子串
//确定遍历顺序
//dp[i][j]依赖于dp[i+1][j-1]，则从下往上，从前往后
//举例推导dp数组
int result = 0;
boolean[][] dp = new boolean[s.length()][s.length()];
for(int i=s.length()-1;i>=0;i--){
for(int j=i;j<s.length();j++){
if(s.charAt(i)==s.charAt(j)){
if(i==j||i==j-1||dp[i+1][j-1]==true){
dp[i][j] = true;
result++;
}
}
}
}
return result;
}
}
//我的想法，用回溯？判断是否回文，是则加入result中
//回溯算法三要素
//回溯函数的参数和返回值
//字符串以及startIndex
//回溯函数的终止条件
//若字符串到最后则返回
//回溯函数的执行逻辑
//若startIndex到i为回文串则加入到结果集中
//正着读和倒着读一样的字符串
//dp[i][j] 遍历到[i-1,j-1]里面回文子串的数目，
// 确定递推公式
// 若[i-1,j-1]为回文子串，则dp[i][j] = Math.max(dp[i-1][j]+1,dp[i][j-1]+1)
// 若[i-1,j-1]不为回文子串,dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
// dp数组初始化
// 都为0
// 确定遍历顺序
// 从上往下从左至右
/*int[][] dp = new int[s.length()+1][s.length()+1];
for(int i=1;i<=s.length();i++){
for(int j=i;j<=s.length();j++){
if(isValid(s,i-1,j-1)){
dp[i][j] = Math.max(dp[i-1][j]+1,dp[i][j-1]+1);
}else{
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
}
}
}/
return dp[s.length()][s.length()];
//backTracking(s,0);
//return resultPath.size();
}
boolean isValid(String s,int i,int j){
//判断是否是回文
while(i<j){
if(s.charAt(i)!=s.charAt(j)){
return false;
}
i++;
j--;
}
return true;
}
/*void backTracking(String s,int startIndex){
if(startIndex==s.length()){
return ;
}
for(int i=startIndex;i<s.length();i++){
if(isValid(s,startIndex,i)){
String sub = s.substring(startIndex,i+1);
if(isValid(sub)){
resultPath.add(sub);
}
}else{
continue;
}
backTracking(s,startIndex+1);
}
}
boolean isValid(String s){
//判断是否是回文
int i=0;
int j=s.length()-1;
while(i<j){
if(s.charAt(i)!=s.charAt(j)){
return false;
}
i++;
j--;
}
return true;
}*/
//}? ? ? ? ? ? ? ? ? ?
力扣题目链接(opens new window)给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。
示例 1: 输入: "bbbab" 输出: 4 一个可能的最长回文子序列为 "bbbb"。
示例 2: 输入:"cbbd" 输出: 2 一个可能的最长回文子序列为 "bb"。
? ? ? ? dp[i][j]记录所有和i相等的j 的个数当成回文串
? ? ? ? 写出来发现不符合题意，比如说aabaa也是回文串，但是a的个数为4 ，串长度为5
? ? ? ? 求的是串的长度
????????
? ? ? ? 用动态规划，若i==j 则看i和j之间回文串的最大长度
? ? ? ? (选中两个单词，看中间回文串的最大长度)
? ? ? ? 确定dp数组和每个下标的含义
? ? ? ? dp[i][j],看i和j之间回文串的最大长度
? ? ? ??
????????
? ? ? ? 确定递推公式
? ? ? ? ? ? ? ?若s[i]==s[j] 则dp[i][j] = dp[i+1][j-1]+2?
? ? ? ? ? ? ? ? 若s[i]!=s[j] 看选中其中一个字符的最长回文是多少，则
????????????????????????????????dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
????????dp数组初始化
? ? ? ? 当i==j时，一定时回文，全都初始化为1? ??
? ? ? ? 确定遍历顺序
? ? ? ? dp[i][j] 依赖于 dp[i+1][j-1] 则可以从下往上，从左往右进行遍历
? ? ? ? 举例推导dp数组? ? ? ? ? ?
? ? ? ? 打印dp数组
? ? ? ? 遍历时记录true的个数，返回总数，就是回文子串的个数了
? ? ? ?理解一下回文的含义
? ? ? ? 回文串记得通过[i,j]中间的来进行判断，相等时不要忘了dp[i+1][j-1] +2?
? ? ? ? 做的时候忘了+2了
????????
class Solution {
public int longestPalindromeSubseq(String s) {
//卡哥的思路
//dp[i][j] 记录[i~j]的最长的回文子序列
//确定递推公式
//若s[i]==s[j] 则看两者间最长的回文子序列是多少 dp[i][j] = dp[i+1][j-1]+2 加了两个字符，所以加2
//若s[i]!=s[j] 则看选中s[i] 于选中s[j]的两个序列中，最长的回文子序列是多少(两者的最大值)
// dp[i][j] = max(dp[i+1][j],dp[i][j-1])
//确定遍历顺序
//由于dp依赖于dp[i+1][j-1]则dp[i][j]遍历顺序为由下往上，从左往右
//dp数组初始化
//当i==j时一定是回文，所以dp[i][i]=1
int[][] dp = new int[s.length()][s.length()];
for(int i=0;i<s.length();i++){
dp[i][i]=1;
}
for(int i=s.length()-2;i>=0;i--){
for(int j=i+1;j<s.length();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]);
}
}
}
//返回0~length-1的最大值
return dp[0][s.length()-1];
/*
//我的思路：和之前那道题思路一样？ 想着所有和i相等的都是回文，其实是错误的比如bbabb 回文长度为5 我为4
//若i==j dp[i][j] = dp[i][j-1]+1
//若i!=j dp[i][j] = dp[i][j-1]
//确定dp的参数和下标的含义
//i-1~j-1之间以i开头最长的子序列的长度
//确定递推公式
//若s[i-1]==s[j-1] dp[i][j] = dp[i][j-1]+1
//若s[i-1]!=s[j-1] dp[i][j] = dp[i][j-1]
//dp数组初始化
//默认为0
//确定遍历顺序
//从上往下，从左至右
//举例推导dp数组
int[][] dp = new int[s.length()+1][s.length()+1];
int max = 0;
for(int i=1;i<s.length()+1;i++){
for(int j=i;j<s.length()+1;j++){
if(s.charAt(i-1)==s.charAt(j-1)){
dp[i][j] = dp[i][j-1]+1;
if(dp[i][j]>max){
max = dp[i][j];
}
}else{
dp[i][j] = dp[i][j-1];
}
}
}
return max;*/
}
}