题目
题目链接：
https://www.nowcoder.com/practice/6d29638c85bb4ffd80c020fe244baf11
思路
https://blog.csdn.net/qq_36544411/article/details/120021203
思路
动态规划法，
我们以dp[i][j]表示在s1中以第i个元素结尾，s2中以第j个元素结尾的字符串的最长公共子序列长度，
若是i与j相等，则该问题可以变成1+dp[i−1][j−1]，即最长公共子序列长度加1，若是不相等，
则换成两个子问题：dp[i][j−1]或者dp[i−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])
反推求出子序列。只需要求其中一个。
参考答案Java
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) {
/*
https://blog.csdn.net/qq_36544411/article/details/120021203
思路
动态规划法，
我们以dp[i][j]表示在s1中以第i个元素结尾，s2中以第j个元素结尾的字符串的最长公共子序列长度，
若是i与j相等，则该问题可以变成1+dp[i−1][j−1]，即最长公共子序列长度加1，若是不相等，
则换成两个子问题：dp[i][j−1]或者dp[i−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])
反推求出子序列。只需要求其中一个。
*/
int n = s1.length();
int m = s2.length();
int[][] dp = new int[n + 1][m + 1];
for (int i = 0; i <= n ; i++) {
for (int j = 0; j <= m ; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 0;
} else {
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]);
}
}
}
}
Stack<Character> stack = new Stack<>();
while (n > 0 && m > 0) {
if (s1.charAt(n - 1) == s2.charAt(m - 1)) {
stack.add(s1.charAt(n - 1));
n--;
m--;
} else if (dp[n - 1][m] >= dp[n][m - 1]) {
n--;
} else {
m--;
}
}
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) {
sb.append(stack.pop());
}
return sb.length() == 0 ? "-1" : sb.toString();
}
}
参考答案Go
package main
import "fmt"
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* longest common subsequence
* @param s1 string字符串 the string
* @param s2 string字符串 the string
* @return string字符串
*/
func LCS(s1 string, s2 string) string {
/*
https://blog.csdn.net/qq_36544411/article/details/120021203
思路
动态规划法，
我们以dp[i][j]表示在s1中以第i个元素结尾，s2中以第j个元素结尾的字符串的最长公共子序列长度，
若是i与j相等，则该问题可以变成1+dp[i−1][j−1]，即最长公共子序列长度加1，若是不相等，
则换成两个子问题：dp[i][j−1]或者dp[i−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])
反推求出子序列。只需要求其中一个。
*/
n := len(s1)
m := len(s2)
dp := make([][]int, n+1)
for i := 0; i <= n; i++ {
dp[i] = make([]int, m+1)
}
for i := 0; i <= n; i++ {
for j := 0; j <= m; j++ {
if i == 0 || j == 0 {
dp[i][j] = 0
} else {
if s1[i-1] == s2[j-1] {
dp[i][j] = dp[i-1][j-1] + 1
} else {
cur1 := dp[i-1][j]
cur2 := dp[i][j-1]
if cur1 > cur2 {
dp[i][j] = cur1
} else {
dp[i][j] = cur2
}
}
}
}
}
stack := []byte{}
for n > 0 && m > 0 {
if s1[n-1] == s2[m-1] {
stack = append(stack, s1[n-1])
n--
m--
} else if dp[n-1][m] >= dp[n][m-1] {
n--
} else {
m--
}
}
s3 := ""
for k := len(stack) - 1; k >= 0; k-- {
s3 = fmt.Sprintf("%s%s", s3, string(stack[k]))
}
if len(s3) == 0 {
return "-1"
} else {
return s3
}
}
参考答案PHP
<?php
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* longest common subsequence
* @param s1 string字符串 the string
* @param s2 string字符串 the string
* @return string字符串
*/
function LCS( $s1 , $s2 )
{
/*
https://blog.csdn.net/qq_36544411/article/details/120021203
思路
动态规划法，
我们以dp[i][j]表示在s1中以第i个元素结尾，s2中以第j个元素结尾的字符串的最长公共子序列长度，
若是i与j相等，则该问题可以变成1+dp[i−1][j−1]，即最长公共子序列长度加1，若是不相等，
则换成两个子问题：dp[i][j−1]或者dp[i−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])
反推求出子序列。只需要求其中一个。
*/
$n=strlen($s1);
$m= strlen($s2);
$dp=array();
for($i=0;$i<=$n;$i++){
for($j=0;$j<=$m;$j++){
if($i==0 || $j==0){
$dp[$i][$j]=0;
}else{
if($s1[$i-1] == $s2[$j-1]){
$dp[$i][$j]=$dp[$i-1][$j-1]+1;
}else{
$cur1= $dp[$i-1][$j];
$cur2 = $dp[$i][$j-1];
if($cur1>$cur2){
$dp[$i][$j] = $cur1;
}else{
$dp[$i][$j] = $cur2;
}
}
}
}
}
$stack = array();
$idx=0;
while ($n>0 && $m>0){
if($s1[$n-1] == $s2[$m-1]){
$stack[$idx++] = $s1[$n-1];
$n--;
$m--;
}else if($dp[$n-1][$m]>= $dp[$n][$m-1]){
$n--;
}else{
$m--;
}
}
if($idx==0) return "-1";
$s3="";
for(--$idx;$idx>=0;$idx--){
$s3.=$stack[$idx];
}
return $s3;
}
