LeetCode: 115. Distinct Subsequences

1. 완전탐색

완전탐색으로 짜잔하고 풀리면 hard일리가 없지. 역시 Time Out

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        self.answer = 0
        self.dfs(s, t)
        return self.answer
        
    def dfs(self, s, t):
        if not t:
            self.answer += 1
            return
        target = t[0]
        for i, char in enumerate(s):
            if char == target:
                self.dfs(s[i+1:], t[1:])

 

2. DP

문자열을 탐색 혹은 비교하는 문제는 대부분 DP인 경우가 많다.

말그대로 dp다. 문제는 이것도 Time Out

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        dp = [[0] * (len(s)+1) for _ in range(len(t)+1)]
        dp[0][0] = 1
        
        for i in range(1, len(t)+1):
            for j in range(1, len(s)+1):
                if s[j-1] == t[i-1]:
                    for k in range(j):
                        dp[i][j] += dp[i-1][k]
        
        return sum(dp[len(t)])

 

3. (2)의 개선

for문이 3중첩인게 영 마음에 안든다.

애초에 DP Table이 for문 2번으로 읽히도록 만들자.

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        dp = [[0] * (len(s)+1) for _ in range(len(t)+1)]
        for i in range(len(s)+1):
            dp[0][i] = 1
        for i in range(1, len(t)+1):
            for j in range(1, len(s)+1):
                if s[j-1] == t[i-1]:
                    dp[i][j] = dp[i-1][j-1] + dp[i][j-1]
                else:
                    dp[i][j] = dp[i][j-1]
        return dp[len(t)][len(s)]

알고리즘은 아래 그림을 참고하면 된다.

통과인데 살짝 느리네... 더 좋은 방법이 있나?