Java에서 가장 긴 공통 하위 시퀀스 문제를 해결하는 방법-java지도 시간-php.cn

1. 간략한 설명:

Description

두 문자열 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!