Scribbling

class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: self.ret = [] self.helper(nums, []) return self.ret def helper(self, nums, path): self.ret.append(path) if not nums: return for i, num in enumerate(nums): self.helper(nums[i+1:], path+[num])

First: O(N) solution. However, is_satisfied function is not very efficient. class Solution: def minWindow(self, s, t): ret = '' from collections import Counter c = Counter(t) chars = c.keys() j = 0 for i, char in enumerate(s): if char in chars: c[char] -= 1 if self.is_satisfied(c): if not ret or (i - j + 1)

class Solution: def combine(self, n: int, k: int) -> List[List[int]]: self.ret = [] self.helper([i+1 for i in range(n)], k, []) return self.ret def helper(self, nums, k, path): if k == 0: self.ret.append(path) return for i, num in enumerate(nums): self.helper(nums[i+1:], k-1, path+[num])

We already know that all the elements are in [0, 1, 2]. So, we count each element's frequencies. class Solution: def sortColors(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ count = [0] * 3 for num in nums: count[num] += 1 count[2] = count[1] + count[0] count[1] = count[0] for i in range(count[1]): nums[i] = 0 for i in range(count[1], count[2]): nu..

class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: if target matrix[-1][-1]: return False m, n = len(matrix), len(matrix[0]) row = 0 # row search l, r = 0, m - 1 while l target: r = mid - 1 else: row = max(row, mid) l = mid + 1 # column search l, r = 0, n - 1 while l

class Solution: def setZeroes(self, matrix: List[List[int]]) -> None: """ Do not return anything, modify matrix in-place instead. """ m, n = len(matrix), len(matrix[0]) for y in range(m): for x in range(n): if matrix[y][x] == 0: self.inspect_row(matrix, y, x) self.inspect_column(matrix, y, x) elif matrix[y][x] == 'row inspected zero': self.inspect_column(matrix, y, x) elif matrix[y][x] == 'colum..

class Solution: def minDistance(self, word1: str, word2: str) -> int: m, n = len(word1), len(word2) dp = [[0] * (m+1) for _ in range(n+1)] for i in range(1, m+1): dp[0][i] = i for i in range(1, n+1): dp[i][0] = i for i in range(1, n+1): for j in range(1, m+1): if word1[j-1] != word2[i-1]: dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1 else: dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]+1, dp..

class Solution: def simplifyPath(self, path: str) -> str: stack = [] paths = path.split('/') for path in paths: if path: if path == '.': continue elif path == '..': if stack: stack.pop() else: stack.append(path) ret = '/' for path in stack: ret += path + '/' if not stack: return ret return ret[:-1]

class Solution: def mySqrt(self, x: int) -> int: ret = 0 l, r = 0, x while l x: r = mid - 1 else: ret = max(ret, mid) l = mid + 1 return ret

class Solution: def addBinary(self, a: str, b: str) -> str: if len(b) > len(a): a, b = b, a b = '0'*(len(a)-len(b)) + b ret = '' carry = 0 for i in range(len(a)-1, -1, -1): temp = int(a[i]) + int(b[i]) + carry ret += str(temp%2) carry = temp//2 if carry: ret += str(1) return ret[::-1]