Review list

127. Word Ladder

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        words = set(wordList)
        def bfs():
            seen = {beginWord}
            Q = collections.deque([(beginWord, 0)])
            while Q:
                w, d = Q.popleft()
                if w == endWord:return d+1
                for i,c in enumerate(w):
                    for k in string.ascii_lowercase:
                        new_word = w[:i]+k+w[i+1:]
                        if new_word in words and new_word not in seen:
                            seen.add(new_word)
                            Q.append((new_word, d+1))
            return 0
        return bfs()

253. Meeting Rooms II

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        events = []
        for s, e in intervals:
            events.append((s,1))
            # set end as 0 to make sure when we have a same time as end and start, the end will appear before the start event.
            events.append((e,0))
        events.sort()
        available = 0
        room = 0
        for t, event in events:
            if event==1:
                if available==0:
                    room+=1
                else:
                    available -= 1
            else:
                available += 1
        return room

347. Top K Frequent Elements

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        cnt = collections.Counter(nums)
        heap = []
        for key, freq in cnt.items():
            if len(heap)==k:
                heapq.heappushpop(heap, (freq, key))
            else:
                heapq.heappush(heap,(freq, key))
        return [key for _, key in heap]

20. Valid Parentheses

class Solution:
    def isValid(self, s: str) -> bool:
        if not s:return True
        d = {']':'[',
             ')':'(',
            '}':'{'}
        stack = []
        for c in s:
            if c in d:
                if not stack or stack[-1]!=d[c]:return False
                stack.pop()
            else:
                stack.append(c)
        return len(stack)==0

380. Insert Delete GetRandom O(1)

class RandomizedSet:
def __init__(self):
        """
        Initialize your data structure here.
        """
        self.nums = []
        self.d = {}
def insert(self, val: int) -> bool:
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        """
        if val not in self.d:
            self.d[val] = len(self.nums)
            self.nums.append(val)
            return True
        return False
def remove(self, val: int) -> bool:
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        """
        if val in self.d:
            idx = self.d[val]
            # swap the last item and the item which has value of val
            # swap the content and update the index of the last element from the self.d
            self.nums[idx] = self.nums[-1]
            self.d[self.nums[idx]] = idx
            self.nums.pop()
            del self.d[val]
            return True
        return False
def getRandom(self) -> int:
        """
        Get a random element from the set.
        """
        return random.choice(self.nums)
# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

139. Word Break

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        words = set(wordDict)
        from functools import lru_cache
        @lru_cache(None)
        def dfs(word):
            if not word or word in words:return True
            w = ""
            for i,c in enumerate(word):
                w += c
                if w in words:
                    #print(w)
                    if dfs(word[i+1:]):return True
            return False
        return dfs(s)

173. Binary Search Tree Iterator

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class BSTIterator:
def __init__(self, root: TreeNode):
        self.stack = []
        self._extract(root)
       
    def _extract(self, node):
        while node:
            self.stack.append(node)
            node = node.left
    def next(self) -> int:
        """
        @return the next smallest number
        """
        node = self.stack.pop()
        val = node.val
        if node.right:
            self._extract(node.right)
        return val
def hasNext(self) -> bool:
        """
        @return whether we have a next smallest number
        """
        return len(self.stack)>0
# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()

545. Boundary of Binary Tree

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def boundaryOfBinaryTree(self, root: TreeNode) -> List[int]:
        if not root:return []
        if root.left is None and root.right is None:return [root.val]
        left, right, leaf =[root.val], [], []
        def get_left(node):
            if not node:return
            if node.left is None and node.right is None:return
            left.append(node.val)
            if node.left is not None:get_left(node.left)
            else:get_left(node.right)
        def get_right(node):
            if not node:return
            if node.left is None and node.right is None:return
            right.append(node.val)
            if node.right:get_right(node.right)
            else:get_right(node.left)
        def get_leaf(node):
            if node is None:return
            get_leaf(node.left)
            if node.left is None and node.right is None:
                leaf.append(node.val)
            get_leaf(node.right)
        get_left(root.left)
        get_leaf(root)
        get_right(root.right)
        return left+leaf+right[::-1]