给定两个字符串str1和str2，输出两个字符串的最长公共子序列。如果最长公共子序列为空，则返回"-1"。目前给出的数据，仅仅会存在一个最长的公共子序列
数据范围：
要求：空间复杂度 )
，时间复杂度
[编程题]最长公共子序列(二)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* longest common subsequence
* @param s1 string字符串 the string
* @param s2 string字符串 the string
* @return string字符串
*/
public String LCS (String s1, String s2) {
// write code here
if(s1.length() == 0 || s2.length() == 0){
return "-1";
}
int[][] dp = new int[s1.length()][s2.length()];
String[][] lcstr = new String[s1.length()][s2.length()];
for(int i = 0; i< s1.length(); i++){
for(int j = 0; j<s2.length(); j++){
if(s1.charAt(i)==s2.charAt(j)){
if(i == 0 || j==0){
dp[i][j] = 1;
lcstr[i][j] = String.valueOf(s1.charAt(i));
}else{
dp[i][j] = dp[i-1][j-1] + 1;
lcstr[i][j] = lcstr[i-1][j-1] + String.valueOf(s1.charAt(i));
}
}else{
if(i==0 && j==0){
dp[i][j] = 0;
lcstr[i][j] = "";
}else if(i==0){
dp[i][j] = dp[i][j-1];
lcstr[i][j] = lcstr[i][j-1];
}else if(j==0){
dp[i][j] = dp[i-1][j];
lcstr[i][j] = lcstr[i-1][j];
}
if(i!=0 && j!=0){
dp[i][j] = dp[i][j-1] >= dp[i-1][j] ? dp[i][j-1] : dp[i-1][j];
lcstr[i][j] = dp[i][j-1] >= dp[i-1][j] ? lcstr[i][j-1] : lcstr[i-1][j];
}
}
}
}
if("".equals(lcstr[s1.length()-1][s2.length()-1])){
return "-1";
}
return lcstr[s1.length()-1][s2.length()-1];
}
}
发表于 2024-05-05 21:41:28
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* longest common subsequence
* @param s1 string字符串 the string
* @param s2 string字符串 the string
* @return string字符串
*/
public String LCS (String s1, String s2) {
// write code here
if (s1.equals(s2)) {
return s1;
}
if (s1.equals("") || s2.equals("")) {
return "-1";
}
String [][]result = new String[s1.length() + 1][s2.length() + 1];
for (int i = 0; i < s1.length(); i++) {
StringBuilder string = new StringBuilder("");
for (int j = 0; j < s2.length(); j++) {
if (s1.charAt(i) == s2.charAt(j)) {
if (i == 0 || j == 0) {
string.append(s1.charAt(i));
result[i][j] = string.toString();
} else {
result[i][j] = result[i - 1][j - 1] + s1.charAt(i);
}
} else {
if (i == 0 || j == 0) {
if (i == 0 && j == 0) {
result[i][j] = "";
} else if (i == 0) {
result[i][j] = result[i][j - 1];
} else if (j == 0) {
result[i][j] = result[i - 1][j];
}
} else {
if (result[i - 1][j].length() > result[i][j - 1].length()) {
result[i][j] = result[i - 1][j];
} else {
result[i][j] = result[i][j - 1];
}
}
}
}
}
if (result[s1.length() - 1][s2.length() - 1].equals("")) {
return "-1";
} else {
return result[s1.length() - 1][s2.length() - 1];
}
}
}
编辑于 2024-03-23 10:53:25
回复(0)
public String LCS (String s1, String s2) {
// write code here
int l1=s1.length() ,l2=s2.length();
String[][] dp=new String[l1+1][l2+1];
for(int i=0;i<=l1;i++){
for(int j=0;j<=l2;j++){
if(i==0 || j==0){
dp[i][j]="";
}else if(s1.charAt(i-1)==s2.charAt(j-1)){
dp[i][j]=dp[i-1][j-1]+s1.charAt(i-1);
}else{
dp[i][j]=dp[i-1][j].length()>=dp[i][j-1].length()?dp[i-1][j]:dp[i][j-1];
}
}
}
return dp[l1][l2].equals("")?"-1":dp[l1][l2];
}
发表于 2024-03-03 14:19:04
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* longest common subsequence
* @param s1 string字符串 the string
* @param s2 string字符串 the string
* @return string字符串
*/
public String LCS (String s1, String s2) {
// write code here
int n = s1.length(), m = s2.length();
s1 = " " + s1;
s2 = " " + s2;
int index = 0;
int[][] f = new int[n + 1][m + 1];
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
if(s1.charAt(i) == s2.charAt(j)) {
f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + 1);
index = i;
}
}
}
if(f[n][m] == 0) return "-1";
StringBuilder res = new StringBuilder();
while(n > 0 && m > 0) {
if(s1.charAt(n) == s2.charAt(m)) {
res.append(s1.charAt(n));
n--;
m--;
} else {
if(f[n - 1][m] > f[n][m - 1]) {
n--;
} else m--;
}
}
return res.reverse().toString();
}
}
编辑于 2024-02-10 18:32:01
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* longest common subsequence
* @param s1 string字符串 the string
* @param s2 string字符串 the string
* @return string字符串
*/
int[][] memo;
public String LCS (String s1, String s2) {
// write code here
int m = s1.length();
int n = s2.length();
memo = new int[m+1][n+1];
//务必设-1，简化比较操作。
for(int[] row : memo){
Arrays.fill(row, -1);
}
dp(s1, m, s2, n);
StringBuilder sb = new StringBuilder();
return search(s1, s2, sb);
}
public String search(String s1, String s2, StringBuilder sb){
int m = s1.length();
int n = s2.length();
while(m>0 && n>0){
if(s1.charAt(m-1) == s2.charAt(n-1)){
sb.append(s1.charAt(m-1));
m--;
n--;
}else{
//注意memo中[0][0...n]和[0...m][n]都是-1，下面判断可防止下标越界。因为-1比memo中任何有效的数字都小。所有就会m或n不断减减，直到s1.charAt(m-1) == s2.charAt(n-1)。
if(memo[m-1][n] > memo[m][n-1]){
m--;
}else{
n--;
}
}
}
return sb.length() == 0 ? "-1" : sb.reverse().toString();
}
public int dp(String s1, int i, String s2, int j){
if(i<=0 || j<=0){
return 0;
}
if(memo[i][j] != -1){
return memo[i][j];
}
if(s1.charAt(i-1) == s2.charAt(j-1)){
memo[i][j] = dp(s1, i-1, s2, j-1)+1;
}else{
memo[i][j] = Math.max(dp(s1,i-1,s2,j), dp(s1,i,s2,j-1));
}
return memo[i][j];
}
}
发表于 2023-08-10 16:30:10
回复(0)
public String LCS (String s1, String s2) {
int m=s1.length();
int n=s2.length();
int[][] dp=new int[m+1][n+1];
for(int i=1;i<m+1;i++){
for(int j=1;j<n+1;j++){
if(s1.charAt(i-1)==s2.charAt(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]);
}
}
}
if(dp[m][n]==0) return "-1";
StringBuilder ans=new StringBuilder();
int len=dp[m][n];
while(true){
if(s1.charAt(m-1)==s2.charAt(n-1)){ //s1.length()-1、s2.length()-2
len--;
ans.insert(0,s1.charAt(m-1)); //sb.insert(插入的位置，插入的字符)
if(len<=0) break;
m--;
n--;
}else if(dp[m-1][n]>dp[m][n-1]){
m--;
}else{
n--;
}
}
return ans.toString();
}
发表于 2023-07-22 11:33:49
回复(0)
public String LCS (String s1, String s2) {
// write code her
int m = s1.length();
int n = s2.length();
int[][] dp = new int[m+1][n+1];
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(s1.charAt(i-1)==s2.charAt(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]);
}
}
}
String str = "";
int i = m, j = n;
while (i > 0 && j > 0) {
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
str = s1.charAt(i - 1)+ str;
i--;
j--;
} else if (dp[i - 1][j] >= dp[i][j - 1]) {
i--;
} else {
j--;
}
}
if("".equals(str)){
return "-1";
}
return str;
}
发表于 2023-07-10 23:40:15
回复(0)
public class Solution {
public String LCS (String s1, String s2) {
// 字符串1的长度
int sLen1 = s1.length();
// 字符串2的长度
int sLen2 = s2.length();
// dp数组，初始化高度和宽度分别为两个字符串长度+1
// 目的是方便初始化，如果高度和宽度分别是两个字符串的长度，初始化会比较麻烦
// s1[0,i)和s2[0,j)所构成的最长子序列是dp[i][j]
String[][] dp = new String[sLen1 + 1][sLen2 + 1];
// dp数组初始化
for (int i = 0; i <= sLen1; i++) {
dp[i][0] = "";
}
for (int j = 0; j <= sLen2; j++) {
dp[0][j] = "";
}
// 遍历每一种情况
for (int i = 1; i <= sLen1; i++) {
for (int j = 1; j <= sLen2; j++) {
// 因为长度和宽度都是字符串长度+1，所以这里取字符的时候需要减1，保证不越界
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
// 因为要加入的两个字符一样，所以直接取两个字符加入前的最长公共子序列然后加上这个相等的字符
dp[i][j] = dp[i - 1][j - 1] + s1.charAt(i - 1);
} else {
// 取s1不加入当前字符和s2不加入当前字符的情况中的最长的那个子序列
if (dp[i - 1][j].length() >= dp[i][j - 1].length()) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = dp[i][j - 1];
}
}
}
}
return "".equals(dp[sLen1][sLen2]) ? "-1" : dp[sLen1][sLen2];
}
}
发表于 2023-05-31 09:26:21
回复(0)
1.初始化二维表格
2.循环判断每个字符，将结果填表
3.循环结束时，表格最后一个单元格即为解
import java.util.*;
public class Solution {
/**
* longest common subsequence
* @param s1 string字符串 the string
* @param s2 string字符串 the string
* @return string字符串
*/
public String LCS (String s1, String s2) {
// 初始化表格，横向为s1字符串，纵向为s2字符串
String[][] table = new String[s2.length() + 1][s1.length() + 1];
char s1CH,s2CH; // 用于存储每次 s1 和 s2 两个字符串取出的字符
int s2Index = 0; // 字符串2遍历的索引位置起始为0
// s2字符串索引不越界，while继续
while (s2Index < s2.length()){
//取出s2中对应索引的字符
s2CH = s2.charAt(s2Index);
// 内循环遍历s1字符串
for (int i = 0; i < s1.length(); i++) {
// 取出s1字符串中对应i索引的字符
s1CH = s1.charAt(i);
//两个字符相等时
if(s2CH == s1CH){
// 其实表格中第一行和第一列都是null，作为辅助单元。所以实际上每次往表格中插入值时都是行索引 + 1 ，列索引 + 1
// 如果相等: 就取左斜方单元格的值进行判断, 第一次循环时，左斜方位于辅助单元, 值是null
// 1.如果左斜方单元格为null: 将当前要往表格插入位置table[s2Index+1][i+1] = 当前字符s2CH/s1CH
// 2.反之，将当前要往表格插入位置table[s2Index+1][i+1] = 左斜方单元格字符串 + 当前字符s2CH/s1CH
table[s2Index+1][i+1] = table[s2Index][i] == null ? String.valueOf(s2CH) : table[s2Index][i] + s2CH;
}else{
// 如果不相等时， 取出 当前要往表格插入位置table[s2Index+1][i+1] 的左边单元格 和 上方单元格的值 进行判断
// 1.左单元格，上单元格均为null，则当前要往表格插入位置table[s2Index+1][i+1] = null
// 2.左单元格为null，则当前要往表格插入位置table[s2Index+1][i+1] = 上单元格字符串
// 3.上单元格为null，则当前要往表格插入位置table[s2Index+1][i+1] = 左单元格字符串
// 4.都不为null时，判断两个单元格字符串长度，将最长的字符串赋予当前表格插入位置
if(table[s2Index][i+1] == null && table[s2Index + 1][i] == null){
// 1.左单元格，上单元格均为null，则当前要往表格插入位置table[s2Index+1][i+1] = null
table[s2Index+1][i+1] = null;
}else {
if(table[s2Index][i+1] == null){
// 2.左单元格为null，则当前要往表格插入位置table[s2Index+1][i+1] = 上单元格字符串
table[s2Index+1][i+1] = table[s2Index + 1][i];
}else if(table[s2Index + 1][i] == null){
// 3.上单元格为null，则当前要往表格插入位置table[s2Index+1][i+1] = 左单元格字符串
table[s2Index+1][i+1] = table[s2Index][i+1];
}
// 4.都不为null时，判断两个单元格字符串长度，将最长的字符串赋予当前表格插入位置
else if(table[s2Index][i+1].length() > table[s2Index + 1][i].length()){
table[s2Index+1][i+1] = table[s2Index][i+1];
}else{
table[s2Index+1][i+1] = table[s2Index + 1][i];
}
}
}
}
// s2字符串索引++
s2Index++;
}
// 循环结束，表格二维表格中最后一行最后一列的单元格字符串即为解
// 如果为null，返回-1，反之返回对应的字符串
return table[table.length - 1][table[0].length - 1] == null ? "-1" : table[table.length - 1][table[0].length - 1];
}
}
发表于 2022-11-20 16:45:31
回复(0)
public class Solution {
/**
* longest common subsequence
* @param s1 string字符串 the string
* @param s2 string字符串 the string
* @return string字符串
*/
public String LCS (String s1, String s2) {
// write code here
if (s1 == null || s1.length() == 0) {
return "-1";
}
if (s2 == null || s2.length() == 0) {
return "-1";
}
// dp[i][j]以s1中前i个字符和s2中前j个字符的最长公共子序列
String[][] path = new String[s1.length()][s2.length()];
path[0][0] = s1.charAt(0) == s2.charAt(0) ? s1.charAt(0) + "" : "";
// 第一行
for (int i = 1; i < s2.length(); i++) {
if (s2.charAt(i) == s1.charAt(0)) {
path[0][i] = s1.charAt(0) + "";
} else {
path[0][i] = path[0][i - 1];
}
}
// 第一列
for (int i = 1; i < s1.length(); i++) {
if (s1.charAt(i) == s2.charAt(0)) {
path[i][0] = s2.charAt(0) + "";
} else {
path[i][0] = path[i - 1][0];
}
}
for (int i = 1; i < s1.length(); i++) {
for (int j = 1; j < s2.length(); j++) {
if (s1.charAt(i) == s2.charAt(j)) {
path[i][j] = path[i - 1][j - 1] + s1.charAt(i);
} else {
if (path[i][j - 1].length() > path[i - 1][j].length()) {
path[i][j] = path[i][j - 1];
} else {
path[i][j] = path[i - 1][j];
}
}
}
}
return path[s1.length() - 1][s2.length() - 1].length() > 0 ? path[s1.length() -
1][s2.length() - 1] : "-1";
}
}
发表于 2022-09-06 23:05:16
回复(1)
import java.util.*;
public class Solution {
/**
* longest common subsequence
* @param s1 string字符串 the string
* @param s2 string字符串 the string
* @return string字符串
*/
public String LCS (String s1, String s2) {
// write code here
int m = s1.length(), n = s2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i < m + 1; i ++) {
for (int j = 1; j < n + 1; j ++) {
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else if (dp[i][j - 1] > dp[i - 1][j]) {
dp[i][j] = dp[i][j - 1];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
if (dp[m][n] == 0) return "-1";
int length = dp[m][n];
StringBuffer lcs = new StringBuffer();;
while (true) {
if (s1.charAt(m - 1) == s2.charAt(n - 1)) {
lcs.insert(0, s1.charAt(m - 1));
length -- ;
if (length <= 0) break;
m --;
n--;
} else if (dp[m - 1][n] > dp[m][n - 1]) {
m --;
} else {
n --;
}
}
return lcs.toString();
}
}
发表于 2022-08-13 10:01:57
回复(0)
import java.util.*;
public class Solution {
/**
* longest common subsequence
* @param s1 string字符串 the string
* @param s2 string字符串 the string
* @return string字符串
*/
public String LCS (String s1, String s2) {
if (s1==null||s2==null||s1.length()==0||s2.length()==0){
return "-1";
}
int m=s1.length();
int n=s2.length();
//dp[a][b]，a in [0,m], b in [0,n]，定义为s1长度为a的前缀子串，s2长度为b的前缀子串，两个前缀子串的最大公共子序列
String[][]dp=new String[m+1][n+1];
for (int i=0;i<m+1; ++i){
dp[i][0] = "";
}
for (int j=0;j<n+1; ++j){
dp[0][j] = "";
}
for (int i=1; i<m+1; ++i){
for (int j=1; j<n+1; ++j){
if (s1.charAt(i-1) == s2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1] + s1.substring(i-1,i);
}else {
dp[i][j] = dp[i-1][j].length() > dp[i][j-1].length() ? dp[i-1][j] : dp[i][j-1];
}
}
}
String res = dp[m][n];
return res.isEmpty() ? "-1" : res;
}
}
发表于 2022-08-07 22:03:30
回复(0)
import java.util.*;
public class Solution {
/**
* longest common subsequence
* @param s1 string字符串 the string
* @param s2 string字符串 the string
* @return string字符串
*/
public String LCS (String s1, String s2) {
// write code here
int len1 = s1.length();
int len2 = s2.length();
String[][] dp = new String[len1+1][len2+1];
//初始化
for(int i = 0;i <= len2;i++){
dp[0][i] = "";
}
for(int i = 0; i <= len1; i++){
dp[i][0] = "";
}
for(int i = 1; i <= len1; i++){
for(int j = 1;j <= len2; j++){
if(s1.charAt(i - 1) == s2.charAt( j - 1)){
dp[i][j] = dp[i-1][j-1] + s1.charAt(i-1);
}else{
dp[i][j] = dp[i-1][j].length() > dp[i][j-1].length()? dp[i-1][j]: dp[i][j-1];
}
}
}
return dp[len1][len2] == "" ? "-1" : dp[len1][len2];
}
}
发表于 2022-07-30 21:49:10
回复(0)
求最长公共子序列的长度好说
麻烦的是怎么逆向获取子序列
public String LCS (String s1, String s2) {
if (s1==null || s2==null || s1.length()==0 || s2.length()==0) {
return "-1";
}
int R = s1.length() + 1;
int C = s2.length() + 1;
int[][] dp = new int[R][C];
for (int i = 1; i < R; i++) {
for (int j = 1; j < C; j++) {
if (s1.charAt(i-1)==s2.charAt(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]);
}
}
}
if (dp[R-1][C-1]==0) return "-1";
StringBuilder builder = new StringBuilder();
for (int r=R-1,c=C-1;dp[r][c]>=1;) {
if (s1.charAt(r-1)==s2.charAt(c-1)) {
builder.append(s1.charAt(r-1));
--r;
--c;
} else if (dp[r-1][c]>=dp[r][c-1]) {
--r;
} else {
--c;
}
}
return builder.reverse().toString();
}
发表于 2022-07-22 15:57:03
回复(0)
import java.util.*;
public class Solution {
public String LCS (String s1, String s2) {
if(s1==null || s2==null) return "-1";
int m = s1.length(), n = s2.length();
String[][] dp = new String[m+1][n+1];
for(int i=0; i<=m; i++){
for(int j=0; j<=n; j++){
if(i==0 || j==0) dp[i][j]="";
else if(s1.charAt(i-1) == s2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1] + s1.charAt(i-1);
}else{
if(dp[i-1][j].length() > dp[i][j-1].length()) dp[i][j] = dp[i-1][j];
else dp[i][j] = dp[i][j-1];
}
}
}
if(dp[m][n]=="") return "-1";
return dp[m][n];
}
}
发表于 2022-07-22 15:39:17
回复(0)
问题信息
难度：
44条回答
1841收藏
9727浏览
通过挑战的用户
查看代码-
2023-02-21 14:40:59 -
2023-01-05 22:57:07
-
2023-01-05 10:24:08 -
2022-11-11 00:24:25
-
2022-11-10 22:31:05
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
