Java最长公共子序列问题怎么解决

今天小编给大家分享一下Java最长公共子序列问题怎么解决的相关知识点，内容详细，逻辑清晰，相信大部分人都还太了解这方面的知识，所以分享这篇文章给大家参考一下，希望大家阅读完这篇文章后有所收获，下面我们一起来了解一下吧。

1.简述：

描述

给定两个字符串str1和str2，输出两个字符串的最长公共子序列。如果最长公共子序列为空，则返回"-1"。目前给出的数据，仅仅会存在一个最长的公共子序列

数据范围：

要求：空间复杂度  ，时间复杂度 

示例1

输入：

"1A2C3D4B56","B1D23A456A"

返回值：

"123456"

示例2

输入：

"abc","def"

返回值：

"-1"

示例3

输入：

"abc","abc"

返回值：

"abc"

示例4

输入：

"ab",""

返回值：

"-1"

2.代码实现：

import java.util.*; public class Solution {     public String LCS (String s1, String s2) {         //只要有一个空字符串便不会有子序列         if(s1.length() == 0 || s2.length() == 0)              return "-1";         int len1 = s1.length();         int len2 = s2.length();         //dp[i][j]表示第一个字符串到第i位，第二个字符串到第j位为止的最长公共子序列长度         int[][] dp = new int[len1 + 1][len2 + 1];          //遍历两个字符串每个位置求的最长长度         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] + 1;                 //遇到的两个字符不同                 else                     //来自左边或者上方的最大值                     dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);             }         }         //从动态规划数组末尾开始         int i = len1, j = len2;         Stack<Character> s = new Stack<Character>();         while(dp[i][j] != 0){             //来自于左方向             if(dp[i][j] == dp[i - 1][j])                 i--;             //来自于上方向             else if(dp[i][j] == dp[i][j - 1])                 j--;             //来自于左上方向             else if(dp[i][j] > dp[i - 1][j - 1]){                 i--;                 j--;                 //只有左上方向才是字符相等的情况，入栈，逆序使用                 s.push(s1.charAt(i));             }         }         String res = "";         //拼接子序列         while(!s.isEmpty())             res += s.pop();         //如果两个完全不同，返回字符串为空，则要改成-1         return !res.isEmpty() ? res : "-1";       } }

以上就是“Java最长公共子序列问题怎么解决”这篇文章的所有内容，感谢各位的阅读！相信大家阅读完这篇文章都有很大的收获，小编每天都会为大家更新不同的知识，如果还想学习更多的知识，请关注亿速云行业资讯频道。