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最長公共子序列問題怎么解決”這篇文章的所有內容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學習更多的知識，請關注億速云行業資訊頻道。