[Leetcode]392. Is Subsequence(x)

1. problem : 

https://leetcode.com/problems/is-subsequence/description/?envType=study-plan-v2&envId=leetcode-75

 

2. solution 1 :

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        i,j = 0,0 
        s_len,t_len = len(s) , len(t) 
        while i < s_len and j < t_len:
            if s[i] == t[j]:
                i += 1 
            j += 1 
        if i == s_len:
            return True 
        return False

 

이 solution은 chat gpt 4o가 짜준 코드이다. two-pointer 접근법이다. i는 s를 순회하고, j는 t를 순회한다. s [i]와 s [j]가 같다면, i +=1을 하고, j +=1을 한다. 만약에 다르다면 s의 i는 건드리지 않고, t의 j만 1 증가한다. 꼭 기억하자.

 

3. solution 2 :

def is_subsequence(a, b):
    m, n = len(a), len(b)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    
    for j in range(n + 1):
        dp[0][j] = True
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = dp[i][j - 1]
    
    return dp[m][n]

# 예제 문자열
a = "abc"
b = "ahbgdc"

# 결과를 확인합니다.
if is_subsequence(a, b):
    print(f'"{a}"는 "{b}"의 부분 문자열입니다.')
else:
    print(f'"{a}"는 "{b}"에 포함되지 않습니다.')

dp를 이용한 풀이법이다. 복잡하다. 

일단 memoization을 할 dp_table부터 만들자. 

    "" a h b g d c
""  T  T T T T T T
a   F  F F F F F F
b   F  F F F F F F
c   F  F F F F F F

||||
||||
\/\/

    "" a h b g d c
""  T  T T T T T T
a   F  T T T T T T
b   F  F F T T T T
c   F  F F F F F T

결과적으로 , a [i-1]과 b [j-1]이 같다면, 나는 그전행의 전열을 참조할 것이다. 그 말인즉슨, a [:i-2] 원소는 b [:j-2]의 substring이 참인지 거짓인지를 담고 있는 결과다. 따라서, True라면 a [:i-1]과 b [:j-1]도 true가 된다. 

 

예를 들어, [1,2,3]이 있다. 이 리스트가 [1,2,5,4,3]의 sublist인지 확인해 보자. [1,2]는 최소한 [1,2]부터 시작해서 [1,2,5], [1,2,5,4], [1,2,5,4,3]이면 모두 만족한다. 그러므로 , [1,2,3]이 만족하기 위해서는 [1,2,5,4]가 [1,2,]를 만족해야 한다. ([1,2,3]의 3은 [1,2,5,4,3]의 마지막원소이기 때문이다.) 

내가 아직 제대로 이해하지 못해서 쉽게 설명을 못했다. dp에 대한 숙련도가 증가하면 더 자세히 설명하겠다.