大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
今天小编给大家分享一下Java最长公共子序列问题怎么解决的相关知识点,内容详细,逻辑清晰,相信大部分人都还太了解这方面的知识,所以分享这篇文章给大家参考一下,希望大家阅读完这篇文章后有所收获,下面我们一起来了解一下吧。
成都创新互联公司主要从事成都网站设计、成都网站制作、网页设计、企业做网站、公司建网站等业务。立足成都服务富锦,十余年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:028-86922220
1.简述:
给定两个字符串str1和str2,输出两个字符串的最长公共子序列。如果最长公共子序列为空,则返回"-1"。目前给出的数据,仅仅会存在一个最长的公共子序列
数据范围:
要求:空间复杂度 ,时间复杂度
输入:
"1A2C3D4B56","B1D23A456A"
返回值:
"123456"
输入:
"abc","def"
返回值:
"-1"
输入:
"abc","abc"
返回值:
"abc"
输入:
"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; Stacks = new Stack (); 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最长公共子序列问题怎么解决”这篇文章的所有内容,感谢各位的阅读!相信大家阅读完这篇文章都有很大的收获,小编每天都会为大家更新不同的知识,如果还想学习更多的知识,请关注创新互联行业资讯频道。