algorithms

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

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)