首頁> Java> java教程> 主體

Java最長公共子序列問題怎麼解決

王林
發布: 2023-04-14 21:40:01
轉載
1091 人瀏覽過

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
         
          s = 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最長公共子序列問題怎麼解決的詳細內容。更多資訊請關注PHP中文網其他相關文章!

相關標籤:
來源:yisu.com
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板
關於我們 免責聲明 Sitemap
PHP中文網:公益線上PHP培訓,幫助PHP學習者快速成長!