23.02.18 Today’s Leetcode

95. Unique Binary Search Trees II (medium)

처음 생각했던 방식은 top-down 느낌의 DFS를 이용하는 방식이었다. 그래서 처음 root node를 만들고 사용한 elements 들을 체크하면서 DFS와 backtracking을 이용하여 Tree를 구축하는 방식으로 구현하였는데, 첫번째 문제는 backtracking으로 구현한 Tree를 copy하는 것에 있어서 deepcopy에 소요되는 time complexity가 존재했고 그로인해 코드가 더러워졌다. 그래서 bottom-up 느낌의 DFS으로 바꾸어 생각해보았다.

기존에 set을 이용하여 element의 사용여부를 체크하는 것을 어짜피 BST 이므로 root node의 value보다 작고, 큰 element들만 사용되기에 left, right를 이용하여 범위를 나누어 구현했다.

class Solution:
    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        @lru_cache(None)
        def dfs(left, right):
            if left > right: return [None]
            if left == right: return [TreeNode(left)]
            ans = []
            for root in range(left, right+1):
                leftNodes = dfs(left, root - 1)
                rightNodes = dfs(root+1, right)
                for leftNode in leftNodes:
                    for rightNode in rightNodes:
                        rootNode = TreeNode(root, leftNode, rightNode)
                        ans.append(rootNode)
            return ans
        
        return dfs(1, n)

조금더 pythonic 한 code

class Solution:
    def generateTrees(self, n: int, k=1) -> List[Optional[TreeNode]]:
        if n<k: 
            return [None]
        tree_list = [TreeNode(i, left, right) 
                     for i in range(k, n + 1) 
                     for left in self.generateTrees(i - 1, k) 
                     for right in self.generateTrees(n, i + 1)]
        return tree_list

처음 구현한 코드는 다음과 같다. 많이 더러움;

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        temp = set()
        for i in range(1, n + 1):
            temp.add(i)
        
        ans = []

        def dfs(origin, node, elements):
            if not elements:
                print(origin)
                ans.append(origin)
                return
            for elem in elements:
                if elem < node.val:
                    node.left = TreeNode(elem)
                    elements.remove(elem)
                    dfs(origin, node.left, elements)
                    elements.add(elem)
                    node.left = None
                else:
                    node.right = TreeNode(elem)
                    elements.remove(elem)
                    dfs(origin, node.right, elements)
                    elements.add(elem)
                    node.right = None

        for i in range(1, n + 1):
            res = TreeNode(i)
            temp.remove(i)
            dfs(res, res, temp)
            temp.add(i)
        return ans

96. Unique Binary Search Trees (medium)

DP, 1번 문제를 조금 변형해서 풀었다.

class Solution:
    def numTrees(self, n: int) -> int:

        dp = [[0 for i in range(n + 1)] for j in range(n + 1)]

        def dfs(n, k):
            if k >= n:
                return 1
            if dp[n][k] > 0:
                return dp[n][k]
            res = 0
            for i in range(k, n + 1):
                res += dfs(i - 1, k) * dfs(n, i + 1)
            dp[n][k] = res
            return res

        return dfs(n, 1)

112. Path Sum (easy)

만약 모든 node의 value값이 양수라면, targetSum이 음수가 되는경우를 pruning하여 최적화 할 수 있다.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        if targetSum == root.val and not root.left and not root.right:
            return True
        res = False
        res |= self.hasPathSum(root.left, targetSum - root.val)
        res |= self.hasPathSum(root.right, targetSum - root.val)
        return res

97. Interleaving String (medium)

알고리즘은 맞았으나, 언어의 한계를 보여주는 느낌.

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s3.length() != s1.length() + s2.length()) {
            return false;
        }
        boolean dp[][] = new boolean[s1.length() + 1][s2.length() + 1];
        for (int i = 0; i <= s1.length(); i++) {
            for (int j = 0; j <= s2.length(); j++) {
                if (i == 0 && j == 0) {
                    dp[i][j] = true;
                } else if (i == 0) {
                    dp[i][j] = dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1);
                } else if (j == 0) {
                    dp[i][j] = dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1);
                } else {
                    dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) || (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
                }
            }
        }
        return dp[s1.length()][s2.length()];
    }
}