求两个字符串s1和s2的最长公共子序列。
这里说明下，子序列是可以不连续字符按顺序组成的字符串。比如字符串democrat的其中一个子序列是dmat。而mdat就不是它的子序列，因为字符出现顺序不符合。
示例：
输入：s1 = "democrat" s2 = "republican"
输出：eca
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}"> 其实本题就是字符串编辑距离的变种，字符串编辑距离会了，此题就会了。就是字符串编辑距离去掉替换操作，就变成了此问题。
设dp[i][j]表示字符串s1的前i个字符与字符串s2前j个字符的最长公共子序列。
当s1[i] == s2[j]时，有 d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] + 1 dp[i][j] = dp[i-1][j-1] + 1 dp[i][j]=dp[i−1][j−1]+1
否则
d
p
[
i
]
[
j
]
=
m
a
x
{
d
p
[
i
−
1
]
[
j
]
d
p
[
i
]
[
j
−
1
]
dp[i][j] = max class="MathJax_Display">
显然dp[0][j]初始化为0。
显然dp[i][0]初始化为0。
/**
* 最大公共子序列
*
* @author hh
* @date 2021-5-16 16:44
*/
public class LongestCommonSubSequence {
public String commonSubSequence(String s1,String s2){
//保存最长子序列
List<Character> subSequences = new LinkedList<>();
//定义dp数组
int[][] dp = new int[s1.length() + 1][s2.length() + 1];
//计算dp数组
for(int i = 1 ; i <= s1.length(); i++){
for(int j = 1; j <= s2.length(); j++){
if(s1.charAt(i-1) == s2.charAt(j -1)){
dp[i][j] = dp[i-1][j-1] +1;
if(subSequences.size() < dp[i][j]){
subSequences.add(s1.charAt(i-1));
}
}else{
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
}
}
}
return subSequences.stream().map(String::valueOf).collect(Collectors.joining());
}
public static void main(String[] args){
String s1 = "democrat";
String s2 = "republican";
LongestCommonSubSequence longestCommonSubSequence = new LongestCommonSubSequence();
System.out.println(longestCommonSubSequence.commonSubSequence(s1,s2));
}
}
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-subsequence
示例 1：
输入：s = “bbbab”
输出：4
解释：一个可能的最长回文子序列为 “bbbb” 。
示例 2：
输入：s = “cbbd”
输出：2
解释：一个可能的最长回文子序列为 “bb” 。
其实本题可以理解为最长公共子序列的变形，我们可以这么想回文子序列的正序和倒序是相同，那么我把字符串s反转表示为s'，那么最终转化为求两字字符串的最长子序列的长度，代码实现如下所示：
public class Solution2 {
public int longestPalindromeSubseq(String s) {
int n = s.length();
//定义dp数组
int[][] dp = new int[n + 1][n + 1];
char[] cs1 = s.toCharArray();
char[] cs2 = new StringBuilder(s).reverse().toString().toCharArray();
//计算dp数组
for(int i = 1 ; i <= n; i++){
for(int j = 1; j <= n; j++){
if(cs1[i-1] == cs2[j -1]){
dp[i][j] = dp[i-1][j-1] +1;
}else{
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
}
}
}
return dp[n][n];
}
public static void main(String[] args){
String s = "aabaaba";
Solution2 solution = new Solution2();
System.out.println(solution.longestPalindromeSubseq(s));
}
}
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
评论记录：
回复评论：