LSC模板（最长公共子序列）

LSC的含义为求最长公共子序列。

现在我们来一道题目来看看：（leetcode 1092）

给出两个字符串 str1 和 str2，返回同时以 str1 和 str2 作为子序列的最短字符串。如果答案不止一个，则可以返回满足条件的任意一个答案。

（如果从字符串 T 中删除一些字符（也可能不删除，并且选出的这些字符可以位于 T 中的 任意位置），可以得到字符串 S，那么 S 就是 T 的子序列）

输入：str1 = "abac", str2 = "cab"
输出："cabac"
解释：
str1 = "abac" 是 "cabac" 的一个子串，因为我们可以删去 "cabac" 的第一个 "c"得到 "abac"。 
str2 = "cab" 是 "cabac" 的一个子串，因为我们可以删去 "cabac" 末尾的 "ac" 得到 "cab"。
最终我们给出的答案是满足上述属性的最短字符串。

看到这道题目的最开始思路为 首先要找到他们的最长子序列，然后在这个基础上面进行拼接，把str1与str2的没有部分拼上。

首先我们来看看怎么找最长子序列：

f[i][j]  i代表str1的前i个字符，j代表str2的前j个字符。

于是我们有了状态转移方程：

        如果 str1[i] == str2[j]   

                f[i][j] = f[i-1][j-1]+1;

        否则 f[i][j] = Math.max(f[i-1][j] , f[i][j-1]);

这样子我们就找到了他们的最长子序列，接着上代码

class Solution {public String shortestCommonSupersequence(String str1, String str2) {int n = str1.length(), m = str2.length();str1 = " " + str1;str2 = " "+str2;int f[][] = new int [n+10] [m+10];for (int i =1;i<=n ;i++) {for (int j=1;j<=m ;j++) {if (str1.charAt(i) == str2.charAt(j)) f[i][j] = f[i-1][j-1]+1;else f[i][j] = Math.max(f[i][j-1], f[i-1][j]);}}StringBuilder sBuilder = new StringBuilder();int i = n , j =m;while(i>0 || j>0) {if (i ==0) sBuilder.append(str2.charAt(j--));else if (j==0) sBuilder.append(str1.charAt(i--));else {if (str1.charAt(i) == str2.charAt(j)) {sBuilder.append(str1.charAt(i));i--; j--;}else if(f[i][j] == f[i-1][j] ) sBuilder.append(str1.charAt(i--));else sBuilder.append(str2.charAt(j--));}}return sBuilder.reverse().toString();}
}

感谢三叶姐提供的思路。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！