[leetcode]1143. Longest Common Subsequence

1143. Longest Common Subsequence

 

Given two strings text1 and text2, return the length of their longest common subsequence.

A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, "ace" is a subsequence of "abcde" while "aec" is not). A common subsequence of two strings is a subsequence that is common to both strings.

 

If there is no common subsequence, return 0.

 

Example 1:

Input: text1 = "abcde", text2 = "ace" Output: 3 Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:

Input: text1 = "abc", text2 = "abc" Output: 3 Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:

Input: text1 = "abc", text2 = "def" Output: 0 Explanation: There is no such common subsequence, so the result is 0.

 

Constraints:

• 1 <= text1.length <= 1000
• 1 <= text2.length <= 1000
• The input strings consist of lowercase English characters only.

class Solution(object):
    def longestCommonSubsequence(self, text1, text2):
        l1 , l2 = len(text1), len(text2)
        
        pre = [0]*(l2+1)
        cur = [0]*(l2+1)
        for i in range(1, l1+1):
            for j in range(1, l2+1):
                if text1[i-1] == text2[j-1]:
                    cur[j] = pre[j-1]+1
                else :
                    cur[j] = max(cur[j-1], pre[j])
            pre, cur = cur, pre
            
        return pre[-1]
        

		t	e	n	s
	0	0	0	0	0
t	0	1	1	1	1
h	0	1	1	1	1
e	0	1	2	2	2

여기서 [t,t]를 보면 't'와 't' 사이에 가장긴 subsequence의 길이를 의미하는거다. 

다음 [t,n]은 ' t'와 'ten'사이에 가장 긴 subsequence의 길이를 의미하는거다

순차적으로 문자가 포함됬을경우를 확인하며 subsequence길이를 업데이트 해주는 것인데

두 문자열의 글자가 같다면 두 문자열에서 그 글자가 포함되지 않은 경우 즉, 왼쪽 위 대각선부분의 값+1을 해주어야 한다.

같지 않다면 현재 단어가 포함되지 않은 상황 즉 , [h,e]에 서 h가 포함되지 않은 상황 (위쪽 값), e가 포함되지 않은 값 (왼쪽 값)중에 큰 값을 

가지도록 하여 현재 상황에서 최대길이를 가지고 있도록 한다. 

 

만약 이 상황에서 subsequence를 구하고 싶다면 

배열의 가장끝부터 체크하면서 큰값의 가장 작은 인덱스를 확인하고 현재 열보다 인덱스가 작은 열에서 다시 확인하고 반복하여 체크하면 된다. 처음에는 e가 있는 열 (3번)에서 2가 끝나는 지점인 (2번행)을 확인하고 

그다음에 h가 있는 열 (2번)에서 (2번행)부터 체크하여 가장 큰값이 언제 끝나는지 확인하고 (1번행)이라는 것을 확인하여 "t,e"라는 것을 알 수 있다.

 

		t	e	n	s
	0	0	0	0	0
t	0	1	1	1	1
h	0	1	1	1	1
e	0	1	2	2	2