Scribbling

First thing I came out with was to use a trie data structure, as it helps us deal with characters efficiently. class StreamChecker: def __init__(self, words: List[str]): self.trie = {} for word in words: node = self.trie for char in word: if char not in node: node[char] = {} node = node[char] node['#'] = '#' self.candidates = [] def query(self, letter: str) -> bool: self.candidates.append(self.t..

1. Using heaps with lazy removal Below code uses 'MyHeap' data structure, a heap with lazy removal. Lazy removal here means, if we have to remove an element, we handle it by using another heap as a trash can. import heapq class MyHeap: def __init__(self, type='min'): self.heap = [] self.removals = [] self.sign = 1 if type == 'min' else -1 def insert(self, elem): heapq.heappush(self.heap, self.si..

We need to deal with ranges to solve this problem. Below is the link of a wonderful solution. https://leetcode.com/problems/range-module/discuss/244194/Python-solution-using-bisect_left-bisect_right-with-explanation Python solution using bisect_left, bisect_right with explanation - LeetCode Discuss Level up your coding skills and quickly land a job. This is the best place to expand your knowledg..

The very first thing to do is looking for matches. We don't need to use any fancy algorithms when looking for matches in this problem because it is guranteed that replacements will not overlap. Now we have matched list in the form of [index, source, target]. If you are planning to replace s directly, it will lead to bad time complexity as you will have to copy all the characters of s each time y..

class Solution: def calculate(self, s: str) -> int: # ' ' is intentionally added, # to mark the end of the given string s # encountering ' ' will add the last number to the stack self.s = s + ' ' self.ptr = 0 return self.calc() def calc(self): num, stack, sign = 0, [], '+' while self.ptr < len(self.s): c = self.s[self.ptr] # if met with '(', # get the evaluated number by recursion if c == '(': s..

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..