动态规划——子序列和回文串问题

动态规划中关于子序列，回文串的几道题整理了一下。

最长子序列

问题：给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
DP思路：（非最优解）

记s(i)，t(j)分别为长度为 i，j 的字符串 s 和字符串 t 。

如果s[i-1]==t[j-1]，最后一位相同，继续比较s[i-2]和t[j-2]，

如果s[i-1]!=t[j-1]，最后一位不同，比较s[i-1]和t[j-2]，

使用一个二维数组d保存子序列的状态，

时间复杂度：O(m*n)

空间复杂度：O(m*n)

java代码：

1	class Solution {
2	public static boolean isSubsequence(String s, String t) {
3	boolean[][] d = new boolean[s.length() + 1][t.length() + 1];
4
5	if (s.length() > t.length()) return false;
6	if (s.length() == 0) return true;
7	for (int j = 0; j < t.length(); j++) { //s长度为0时，一定是t的子序列
8	d[0][j] = true;
9	}
10
11	for (int i = 1; i <= s.length(); i++) {
12	for (int j = 1; j <= t.length(); j++) {
13
14	if (s.charAt(i - 1) == t.charAt(j - 1)) { //如果当前的最后一位相同比较s的前一位和t的前一位
15	d[i][j] = d[i - 1][j - 1];
16
17	} else {
18	d[i][j] = d[i][j - 1]; //否则比较s和t的前一位
19	}
20	}
21	}
22	return d[s.length()][t.length()];
23	}
24	}

其他思路参考： isSubsequence_392

空间复杂度可以继续优化，待更新。

最长回文子串

问题：给定一个字符串 s，找到 s 中最长的回文子串。
DP思路：（目前想到的最优解）
- 中心扩展法
  
  遍历字符串序列，遍历到第i个字符串，以i字符串为中心，向左右扩展回文串，每次保存最大长度的开始和结束坐标。需要注意的细节是，子串长度为1和2时要单独处理，具体看代码。
  
  这里中心的个数一般会错误认为是n，实际上是2n-1，因为2个字母中间的空格，在回文子串长度为偶数时是作为中心的。
  
  时间复杂度：O(n^2)
  
  空间复杂度：O(1)

java代码：

class Solution {
    public String longestPalindrome(String s) {
        //按中心展开 共有2n-1个中心 如果字母数为偶数，每2个元素之间的空格也要算为1个中心
        
        if(s.length()==0) return "";
        
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expend_from_center(s, i, i); // 考虑单个字母时候的len
            int len2 = expend_from_center(s, i, i + 1); //考虑2个字母为回文时候的len
            int len = Math.max(len1, len2);  //保存较长的

            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end+1);
    }

    //以某个字母向两边扩展
    public int expend_from_center(String s, int left, int right) {
        while ((left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right))) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}

回文子串个数

问题：给定一个字符串，计算这个字符串中有多少个回文子串。
DP思路：

中心扩展法，思路同最长回文子串，基本只要加个计数器即可。

时间复杂度：O(n^2)

空间复杂度：O(1)

java代码：

class Solution {
    int num = 0;
    public int countSubstrings(String s) {
        for (int i=0; i < s.length(); i++){
            count(s, i, i);//单个字母肯定是回文，只做了一次num++
            count(s, i, i+1);
        }
        return num;
    }
    
    public void count(String s, int start, int end){
        while(start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)){
            num++;
            start--;
            end++;
        }
    }

}

最长回文子序列

问题：给定一个字符串 s，找到其中最长的回文子序列。
DP思路：

用二维数组dp[n][n]表示长度为 n 的字符串 s 的状态矩阵，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]=MAX(dp[i+1][j],dp[i][j+1])

注意：i 要从后往前遍历

时间复杂度：O(n^2)

空间复杂度：O(n^2)

java代码：

1	class Solution {
2	//动态规划二维数组作为状态矩阵下三角稀疏可优化
3	public static int longestPalindromeSubseq(String s) {
4	if (s.length() == 0) return 0;
5	int dp[][] = new int[s.length()][s.length()];
6	//想清楚为什么从后往前遍历保证了i,j之间的子序列的状态的更新
7	for (int i = s.length() - 1; i >= 0; i--) {
8	dp[i][i] = 1;//单个字母的最长回文子序列一定是1
9	for (int j = i + 1; j < s.length(); j++) {
10	if (s.charAt(i) == s.charAt(j)) {
11	dp[i][j] = dp[i + 1][j - 1] + 2;
12	} else {
13	dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
14	}
15	}
16	}
17	//输出dp数据测试
18	// for (int i = 0; i < s.length(); i++) {
19	// for (int j = 0; j < s.length(); j++) {
20	// System.out.print(dp[i][j]);
21	// }
22	// System.out.println();
23	// }
24
25	return dp[0][s.length() - 1];
26	}
27	}

压缩二维矩阵为一维矩阵，空间复杂度为O(n) 代码：

1	class Solution {
2	//二维数据降为一维数组
3	public int longestPalindromeSubseq(String s) {
4	if (s.length() == 0) return 0;
5
6	int[] pre = new int[s.length()]; // 前一步状态矩阵
7	int[] cur = new int[s.length()]; //当前状态矩阵最后一个元素永远保存当前的最大回文子序列长度
8	for (int i = s.length() - 1; i >= 0; i--) {
9	cur[i] = 1;
10	for (int j = i + 1; j < s.length(); j++) {
11	if (s.charAt(i) == s.charAt(j)) {
12	cur[j] = pre[j - 1] + 2;
13	} else {
14	cur[j] = Math.max(pre[j], cur[j - 1]);
15	}
16	}
17	int[] temp = pre;
18	pre = cur;
19	cur = temp;
20	}
21	return pre[s.length() - 1];
22	}
23	}

1	class Solution {
2	public String longestPalindrome(String s) {
3	//按中心展开共有2n-1个中心如果字母数为偶数，每2个元素之间的空格也要算为1个中心
4
5	if(s.length()==0) return "";
6
7	int start = 0, end = 0;
8	for (int i = 0; i < s.length(); i++) {
9	int len1 = expend_from_center(s, i, i); // 考虑单个字母时候的len
10	int len2 = expend_from_center(s, i, i + 1); //考虑2个字母为回文时候的len
11	int len = Math.max(len1, len2); //保存较长的
12
13	if (len > end - start) {
14	start = i - (len - 1) / 2;
15	end = i + len / 2;
16	}
17	}
18	return s.substring(start, end+1);
19	}
20
21	//以某个字母向两边扩展
22	public int expend_from_center(String s, int left, int right) {
23	while ((left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right))) {
24	left--;
25	right++;
26	}
27	return right - left - 1;
28	}
29	}

1	class Solution {
2	int num = 0;
3	public int countSubstrings(String s) {
4	for (int i=0; i < s.length(); i++){
5	count(s, i, i);//单个字母肯定是回文，只做了一次num++
6	count(s, i, i+1);
7	}
8	return num;
9	}
10
11	public void count(String s, int start, int end){
12	while(start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)){
13	num++;
14	start--;
15	end++;
16	}
17	}
18
19	}