check-if-there-is-a-valid-parentheses-string-path-v1.py (1703B)
1 class Solution: 2 def checkValid(self,hist): 3 stack = [] 4 for ch in hist: 5 if ch == '(': 6 stack.append('(') 7 if ch == ')': 8 if len(stack) > 0: 9 stack.pop() 10 else: 11 return False 12 return len(stack) == 0 13 14 15 def recurse(self,pos_x,pos_y,hist,grid, oc, cc): 16 17 if not self.memo.get(str(pos_x) + " " + str(pos_y) + " " + str(oc) + " " + str(cc)) is None or self.done: 18 return False # true would already be propogated up. 19 20 if pos_y == len(grid)-1 and pos_x == len(grid[pos_y])-1: 21 return self.checkValid(hist + grid[pos_y][pos_x]) 22 23 current = grid[pos_y][pos_x] 24 25 on = oc 26 cn = cc 27 28 if current == '(': 29 on += 1 30 else: 31 cn += 1 32 33 if cn > on: 34 return False 35 36 correct = False 37 38 if(pos_y < len(grid)-1): 39 down_res = self.recurse(pos_x,pos_y+1,hist+current,grid,on,cn) 40 if down_res: 41 correct = True 42 if not correct and (pos_x < len(grid[pos_y])-1): 43 right_res = self.recurse(pos_x+1,pos_y,hist+current,grid,on,cn) 44 if right_res: 45 correct = True 46 47 self.memo[str(pos_x) + " " + str(pos_y) + " " + str(oc) + " " + str(cc)] = correct 48 if correct: 49 self.done = True 50 return correct 51 52 def hasValidPath(self, grid: list[list[str]]) -> bool: 53 # conditions: 54 # () 55 # AB where A is valid, B is valid 56 57 self.memo = {} 58 self.done = False 59 return self.recurse(0,0,"",grid,0,0)