1143. 最长公共子序列
问题描述
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列，则返回 0。
解题思路
二维dp数组：dp[i][j]表示目标串的子串text1.substring(0, i )和text2.substring(0, j )的最长公共子序列的长度
s.substring(int beginIndex，int endIndex)截取规则：beginIndex =< s的值 < endIndex
base case：因为若其中一个子串为空，则公共子序列一定为空，所以dp数组的首行和首列均为0
状态转移：如果text1.charAt(i-1)==text2.charAt(j-1)，则该字符可加入公共子序列，即dp[i][j] = dp[i-1][j-1] + 1；如果text1.charAt(i)！=text2.charAt(j)，则dp[i][j]应该是dp[i-1][j]与dp[i][j-1]中的最大值。
代码实现
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int l1 = text1.length(), l2 = text2.length();
int[][] dp = new int[l1 + 1][l2 + 1];
for(int i = 0; i <= l1; i++){
//base case, text2为空时公共子序列一定为空
dp[i][0] = 0;
if(i == 0) continue;
for(int j = 0; j <= l2; j++){
//base case, text1为空时公共子序列一定为空
dp[0][j] = 0;
if(j == 0) continue;
if(text1.charAt(i - 1) == text2.charAt(j - 1)){
dp[i][j] = dp[i-1][j-1] + 1;
}else{
dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
}
}
}
return dp[l1][l2];
}
}
516. 最长回文子序列
问题描述
给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。
解题思路
二维dp数组：dp[i][j]表示s的子串s.substring(i,j+1)的最长回文子序列长度
s.substring(int beginIndex，int endIndex)截取规则：beginIndex =< s的值 < endIndex
状态转移：如果s.charAt(i)==s.charAt(j)，则该字符可加入到原回文子序列两端，即dp[i][j] = dp[i+1][j-1] + 2；如果text1.charAt(i)！=text2.charAt(j)，则dp[i][j]应该是dp[i+1][j]与dp[i][j-1]中的最大值。
class Solution {
public int longestPalindromeSubseq(String s) {
int l = s.length();
int[][] dp = new int[l][l];
for(int i = l - 1; i >= 0; i--){
int j = 0;
while(j < i){
//当i>j时，substring(i,j)不存在，所以回文子序列长度为0
dp[i][j] = 0;
j++;
}
//i==j时，子串中只有一个字符时，回文子序列长度为1
dp[i][i] = 1;
for(j = i + 1; j < l; 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][l-1];
}
}
