LCS(Longest Common Subsequence) 길이 및 최장 공통 서브시퀀스 문자열 leetcode
14734 단어 javadatastructuredpalgorithms
문자열의 하위 시퀀스는 나머지 문자의 상대 순서를 변경하지 않고 일부 문자(없을 수 있음)가 삭제된 원래 문자열에서 생성된 새 문자열입니다.
예를 들어 "ace"는 "abcde"의 하위 시퀀스입니다.
두 문자열의 공통 하위 시퀀스는 두 문자열에 공통인 하위 시퀀스입니다.
예 1:
Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.
해결책:
상향식 접근(메모이제이션) :
시간 복잡도 :
O(m*n)
여기서 m
및 n
는 두 문자열a
및 b
의 길이입니다.공간 복잡도: o(m*n)
2d dp
및 O(m+n)
를 보조 스택 공간으로 사용하기 때문에 최악의 경우 m+n
재귀 호출을 수행합니다.class Solution {
public int longestCommonSubsequence(String text1, String text2) {
// we will start with the last index if its a match then we will decrement both the index
//else we will decrement text1 index keeping text2 index same and in second method call we will decrement text2 index keeping the text1 index same
// by this we will cover all the possibility
// and we will be able to get substring with the largest length common in both the Strings
// lets optimize with dp
int dp[][] = new int[text1.length()][text2.length()];
for(int row[]: dp) Arrays.fill(row,-1);
return findLcsLength(text1,text2,text1.length()-1,text2.length()-1,dp);
}
public int findLcsLength(String a, String b, int i,int j,int dp[][]){
if(i<0 || j<0) return 0;
if(dp[i][j]!=-1) return dp[i][j];
if(a.charAt(i) ==b.charAt(j)){
return dp[i][j] = 1 + findLcsLength(a,b,i-1,j-1,dp);
}
else {
return dp[i][j]= 0+Integer.max(findLcsLength(a,b,i-1,j,dp),findLcsLength(a,b,i,j-1,dp));
}
}
}
표
class Solution {
public int longestCommonSubsequence(String str1, String str2) {
int dp[][] = new int[str1.length()+1][str2.length()+1];
for(int i=0;i<=str1.length();i++){
dp[i][0] =0;
}
for( int i =0;i<=str2.length();i++){
dp[0][i] = 0;
}
for( int i =1;i<=str1.length();i++){
for(int j =1;j<=str2.length();j++){
if(str1.charAt(i-1)==str2.charAt(j-1)){
dp[i][j] = 1 + dp[i-1][j-1];
}
else dp[i][j] = Integer.max(dp[i][j-1],dp[i-1][j]);
}
}
return dp[str1.length()][str2.length()];
}
}
가장 긴 공통 하위 시퀀스 문자열을 인쇄해야 하는 경우 위 코드에 다음을 추가하기만 하면 됩니다.
int p = str1.length(), q = str2.length();
while(p>0 && q>0){
if(str1.charAt(p-1) == str2.charAt(q-1)){
str = str1.charAt(p-1)+ str;
p--;
q--;
}
else if(dp[p][q-1] > dp[p-1][q]){
q--;
}
else p--;
}
System.out.println(str);
Reference
이 문제에 관하여(LCS(Longest Common Subsequence) 길이 및 최장 공통 서브시퀀스 문자열 leetcode), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/prashantrmishra/length-of-longest-common-subsequence-lcs-leetcode-4833텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)