23.01.21 Today’s Leetcode

93. Restore IP Addresses (medium)

Runtime 43.5%, Memory 5.25%
DFS and backtracking.

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        n = len(s)
        res = []
        def dfs(index, current):
            nonlocal n, res
            if index == n and len(current) == 4:
                res.append(current[:])
                return
            if index >= n:
                return
            if s[index] == '0':
                current.append('0')
                dfs(index + 1, current)
                current.pop()
            else:
                for i in range(1, 4):
                    num = int(s[index:index + i])
                    if num < 0 or num > 255:
                        continue
                    current.append(str(num))
                    dfs(index + i, current)
                    current.pop()
        dfs(0, [])
        temp = ['.'.join(x) for x in res]
        return temp

257. Binary Tree Paths (easy)

# 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 binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        res = []
        def isLeaf(node):
            return node and node.left == None and node.right == None

        def dfs(cur, path):
            nonlocal res
            if isLeaf(cur):
                res.append(path[:])
                return
            
            if cur.left:
                path.append(str(cur.left.val))
                dfs(cur.left, path)
                path.pop()
            if cur.right:
                path.append(str(cur.right.val))
                dfs(cur.right, path)
                path.pop()
            
        dfs(root, [str(root.val)])
        temp = ['->'.join(x) for x in res]
        return temp

133. Clone Graph (medium)

Graph 문제를 풀어봐야 할 것 같아서, 시도해본 새로운 문제들.
python에서 deque라는 자료형을 알게되었다. 평소에 list를 queue나 stack처럼 사용할 수 있다는 것을 알고 있기는 했지만 데이터구조적으로 index를 유지하기 때문에 의미가 없다고 생각했는데, deque라는 데이터구조가 있다는것을 알고 조금 놀랐다.

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node: return node
        
        q, clones = deque([node]), {node.val: Node(node.val, [])}
        while q:
            cur = q.popleft() 
            cur_clone = clones[cur.val]            

            for ngbr in cur.neighbors:
                if ngbr.val not in clones:
                    clones[ngbr.val] = Node(ngbr.val, [])
                    q.append(ngbr)
                    
                cur_clone.neighbors.append(clones[ngbr.val])
                
        return clones[node.val]