题目

题目链接：
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]+1else  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]+1else  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 mainimport "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]+1else  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]+1else  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;
}