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