algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

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)