647. 回文子串

题目描述

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例1：
输入：$s="abc"$
输出：$3$
示例2：
输入：$s="aaa"$
输出：$6$

思路

1、确定dp数组
dp[i][j]表示区间范围[i,j]的字串是否是回文子串，若是则为true，否则为false
2、确定递推公式
s[i]和s[j]不相等时，dp为false
若相等：
1）下标i与j相同，同一个字符例如a，肯定是回文子串
2）下标i与j相差为1，例如aa，也是回文子串
3）下标i与j相差大于1，例如cabac，此时只需看i+1，j-1的位置是否为true即可。
除了动态规划，本题也可以使用双指针，首先找到中心，然后向左右扩散以判断是否为回文串。

解法1

class Solution {public int countSubstrings(String s) {int ans = 0;int len = s.length();if(s == null || len < 1){return 0;}boolean[][] dp = new boolean[len][len];for(int j = 0;j<len;j++){for(int i = 0;i<=j;i++){if(s.charAt(i) == s.charAt(j)){if(j-i < 3){dp[i][j] = true;}else{dp[i][j] = dp[i+1][j-1];}}else{dp[i][j] = false;}}}for(int i = 0;i<len;i++){for(int j = 0;j < len;j++){if(dp[i][j]){ans++;}}}return ans;}
}

解法2

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

解法3

class Solution {public int countSubstrings(String s) {int len = s.length();int ans = 0;if(s == null || len< 1){return 0;}for(int i = 0; i < 2*len-1;i++){int left = i/2,right = left + i%2;while(left >= 0 && right < len && s.charAt(left) == s.charAt(right)){ans++;left--;right++;}}return ans;}
}

总结

本题难点在于，确定dp数组，很容易就会想到以i-1结尾的字符串的回文串长度，就没写出来了。

516. 最长回文子序列

题目描述

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例1：
输入：$s="bbbab"$
输出：$4$
示例2：
输入：$s="cbbd"$
输出：$2$

思路

与上一题相比，回文串换成了回文序列，也就是对元素的相连没有了要求，需要考虑的情况反而少了一些。
1、确定dp数组
dp[i][j]表示字符串s在[i,j]范围内最长的回文子序列的长度为dp[i][j]
2、确定递推公式
若s[i]和s[j]相同，那么dp[i][j] = dp[i+1][j-1]+2
若不相同，则分别加入s[i]、s[j]看那个可以组成最长的回文子序列

解法

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];}
}

总结

动态规划的最后一天了，好好看，好好学