Intuitive Python solution


  • 0
    D

    Simply match up every right parenthesis with a left one as you go through the string, keeping track of the indices of stars and unclosed left parentheses. For each open parenthesis left over after passing through the string, just find a star that came after to cancel it out. I use double ended queues just because I think it makes the code look a little nicer than with indices.

    def checkValidString(self, s):
        opened, stars = deque(), deque()
        for i,c in enumerate(s):
            if c == '(':    opened.append(i)
            elif c == '*':  stars.append(i)
            else:
                if opened:  opened.pop()
                elif stars: stars.pop()
                else:       return False
        
        while opened and stars:
            while stars and stars[0] < opened[0]:
                stars.popleft()
            if stars:
                stars.popleft()
                opened.popleft()
        return not opened

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.