Scribbling

Using double trie structures for prefix and suffix. Somewhat straightforward if one already knows about trie. If not, refer to "LeetCode prob 208. Implement Trie (Prefix Tree)". class WordFilter: def __init__(self, words: List[str]): wordDict = {} for idx, word in enumerate(words): wordDict[word] = idx self.PrefixTree = {} self.SuffixTree = {} for word, idx in wordDict.items(): node = self.Prefi..

class Solution: def getOrder(self, tasks: List[List[int]]) -> List[int]: import heapq ret = [] TaskHeap = [] WaitHeap = [] for idx, task in enumerate(tasks): heapq.heappush(TaskHeap, (task[0], idx, task[1])) curTime = 0 while True: if not WaitHeap: if not TaskHeap: break startTime, idx, processTime = heapq.heappop(TaskHeap) heapq.heappush(WaitHeap, (processTime, idx, startTime)) while TaskHeap a..

class Solution: def trapRainWater(self, heightMap: List[List[int]]) -> int: import heapq boundaries = [] m, n = len(heightMap), len(heightMap[0]) visited = [[False] * n for _ in range(m)] for y in range(m): for x in range(n): if y == 0 or y == m - 1 or x == 0 or x == n - 1: heapq.heappush(boundaries, (heightMap[y][x], y, x)) visited[y][x] = True ret = 0 dy, dx = [0, 1, 0, -1], [1, 0, -1, 0] whil..

class Solution: def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int: from math import atan2, pi from bisect import bisect_right numLoc = 0 angles = [] for point in points: x, y = point[0] - location[0], point[1] - location[1] if x == 0 and y == 0: numLoc += 1 else: val = atan2(y, x) * 180 / pi if val < 0: val += 360 angles.append(val) angles.sort() angles += ..

Key observations needed to solve this prob are as below. 1) There is no need to push the same button twice, as it doesn't make any change. 2) Sequence of buttons doesn't matter. In the provided example, a possible solution was (1,0)->(0,1)->(1,1). However, any sequences of the three buttons produce the same result. Functions we need: 1) isComplete(): checks whether matrix only has zeros or not 2..

Solution below is not very efficient, however, is seemingly intuitive and easy to understand. The core idea is to reuse solution for "57. Insert Interval". (Link: https://leetcode.com/problems/insert-interval/) The problem is about inserting an interval such that intervals are sorted in ascending order while not having any overlapping intervals. We can use exactly the same idea to implement "add..

class Solution: def longestStrChain(self, words: List[str]) -> int: ret = 1 # First, we sort words by its length # By this way, we only need to check the previous length (or current length - 1) # That is, if the length(word) is k, # We only need to check words that have length of k - 1. words.sort(key=lambda word: len(word)) # dp[word]: max chain length until the word dp = {} for word in words: ..

class Solution: def equationsPossible(self, equations: List[str]) -> bool: # Define parents list for find/union parent operations parents = [i for i in range(26)] # find parent operation def find_parent(node): if node == parents[node]: return node parents[node] = find_parent(parents[node]) return parents[node] # union parent operation def union_parent(node1, node2): node1 = find_parent(node1) no..

All we have to do is traversing every node by dfs and checking whether current node's structure is already seen or not. Then, we need to come up with a way to 'represent' a tree's structure. Here, we use a string to represent the tree structure. --> str(node.val) + (left tree structure) + (right tree structure) If it is a new string, we add to our dictionary (self.dp). If it is a already seen st..

First, we look through all the transactions and check how much money(or debt) each one has. Array self.money is storing that information, and we excluded the ones who don't have any money or debt. Next, let's define "helper(self, indexs)" as our goal function. It will return 'min # of transactions needed'. Here, we take indexes (tuple type) as the parameter of the function so that we can easily ..