Long Pressed Name LeetCode solution in Python

1
class Solution:
2
    def isLongPressedName(self, name: str, typed: str) -> bool:
3
        # dic for memoization
4
        dic = {}
5

6
        def dfs(i, j):
7
            if (i, j) in dic:
8
                return dic[(i, j)]
9

10
                # see if there is any case where both i and j reach to the end, cuz that will be the true condition
11
                # I only need one True
12
            if i >= len(name):
13
                return j == len(typed)
14
                # we iterated through the end of typed, and not yet for name
15
            if j >= len(typed):
16
                return False
17

18
                # if the characters don't match, return False
19
            if name[i] != typed[j]:
20
                dic[(i, j)] = False
21
                return False
22

23
                # if the two characters match
24
                # two options, either you move on (dfs(i + 1, j + 1)) or you consider it as an extra character (dfs(i, j + 1))
25
                # return if any of them is True, which means that i, j reach to the end as aforementioned
26
            dic[(i, j)] = dfs(i + 1, j + 1) or dfs(i, j + 1)
27
            return dic[(i, j)]
28

29
            # start from index 0, 0
30

31
        return dfs(0, 0)