Day 47 of LeetCode

Documenting LeetCode solving.

Q123

115. Distinct Subsequences

Hard. DP

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        dp = {}

        def dfs(i, j):
            if j == len(t):
                return 1
            if i == len(s):
                return 0
            if (i, j) in dp:
                return dp[(i, j)]

            if s[i] == t[j]:
                # i and j both move 1 step + i move 1 step
                dp[(i, j)] = dfs(i + 1, j + 1) + dfs(i + 1, j)
            else:
                dp[(i, j)] = dfs(i + 1, j)

            return dp[(i, j)]

        return dfs(0, 0)

Q124

72. Edit Distance

Medium. 2D DP, bottom up.

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        cache = [ [float("inf")] * (len(word2) + 1) for _ in range((len(word1) + 1)) ]
        # fill out the last row
        for j in range(len(word2) + 1):
            cache[len(word1)][j] = len(word2) - j
        # fill out the last column
        for i in range(len(word1) + 1):
            cache[i][len(word2)] = len(word1) - i

        for i in range(len(word1) - 1, -1, -1):
            for j in range(len(word2) - 1, -1, -1):
                if word1[i] == word2[j]:
                    cache[i][j] = cache[i + 1][j + 1]
                else:
                    cache[i][j] = 1 + min(
                                    cache[i + 1][j],     # delete
                                    cache[i + 1][j + 1], # replace
                                    cache[i][j + 1],     # insert
                                  )

        return cache[0][0]