LC79 Word Search

class Solution: def exist(self, board: List[List[str]], word: str) -> bool: # time O( M * N * 4^L ), where M*N is size of board, L is length of target word. space O(L) if not board: return False row = len(board) col = len(board[0]) # why using two for loop?... [Read More]

LC980 Unique Paths III

class Solution: # main idea: count all the cells which are == 0, then get the coordinate x,y; try four directions until reached to grid[i][j] == 2 ; check if cnt has been decresed to 0, if yes, path increament by 1 # time O(3^(N-1)) space O(N) beceuse of stack... [Read More]

LC698 Partition to K Equal Sum Subsets

# time O(K*2^N) class Solution: def canPartitionKSubsets(self, nums: List[int], k: int) -> bool: if k <2 : return True size = len(nums) if size < k: return False target = sum(nums)/k visited = [0]* size return self.dfs(0,nums,visited,0,k,target) def dfs(self, start, nums, visited, sum, k, target): if k == 1: return... [Read More]
Tags: DP Recursion