23.01.10 Today’s Leetcode

101. Same Tree (Easy)

BST를 이용한 Solution. leaf node까지도 비교해야하기 때문에 append할때 None을 걸러주지 않는다.

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        p_queue, q_queue = [p], [q]
        while p_queue and q_queue:
            a, b = p_queue.pop(0), q_queue.pop(0)
            if a == None and b == None:
                continue
            elif a == None or b == None:
                return False
            elif a.val != b.val:
                return False
            
            p_queue.append(a.left)
            p_queue.append(a.right)
            q_queue.append(b.left)
            q_queue.append(b.right)
        return True

Delete Operation for Two String (medium, DP)

DP를 사용하는 solution은 언제나 떠올리기 힘들다. 문제를 풀 때, 문제를 따라가면 그냥 풀리는 경우가 (50%) 이고 재귀적으로나 수학적으로 풀이하는게 (20%) 라면 나머지 (30%)는 대부분이 이런 문제이거나 기상천외한 방식으로 문제를 푸는 것 같다. 사실 recursive하게 접근해보려는 시도가 있었다면, DP를 이용해서 최적화 하는 방식도 고려해야하는데 여기까지 생각이 미치지 않는것 같다. 많은 문제를 풀어보면서 접근방식에 대한 다양화가 필요하다.

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m = len(word1)
        n = len(word2)
        dp = [[0] * (n + 1) for x in range(m + 1)]
        # dp[i][j] means that minDistance between word1[:i] and word2[:j]
        # 놀랍게도 내가 적은 주석이다.
        for i in range (m + 1):
            dp[i][0] = i
        for j in range (n + 1):
            dp[0][j] = j
        for i in range (1, m + 1):
            for j in range (1, n + 1):
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + 1
        return dp[-1][-1]