Python solution with clear explanation


  • 0

    Problems

    For this solution, we only want to find those two situations:

    1. If the current char is the back parenthesis: is it the corresponding parenthesis of last added parenthesis
    2. If the current char is the front parenthesis: add it to our pending structure

    Solutions

    • From the requirements above, we know using a stack is the best choice.

    • How to relate the front parenthesis with back parenthesis?
      We can use a dictionary, where the keys are the back parenthesis while the values are the front parenthesis.

    • The pros of using a dict is determining whether element is a key or value only requires O(1) time complexity. x in dic and x in dic.viewvalues()


    def isValid(self, s):
        dic = {']' : '[', '}' : '{', ')' : '('}
        stack = []
        for char in s:
            if char in dic.viewvalues():
                stack.append(char)
            elif char in dic:
                if not stack or stack.pop() != dic[char]:
                    return False
        return True if not stack else False

  • 1
    N

    I liked your solution but you can make things a bit shorter and clearer by noticing a few things:

    1. There's no need to elif char in dic because by the assumptions of the question ("containing just the characters..." ) you know that if it's not an opening parentheses, it's a closing one.
    2. While I know that not stack checks both for None and an empty list, I prefer len(stack) == 0 as it's much clearer. (It's a question of taste but that's just my opinion)
    3. Instead of return True if not stack else False, you can do: return not stack or return len(stack) == 0

    Here's what I coded:

    class Solution(object):
        def isValid(self, s):
            pairs, stack = {'[': ']', '{': '}', '(': ')'}, []
            for char in s:
                if char in pairs:
                    stack.append(char)
                elif len(stack) == 0 or pairs[stack.pop()] != char:
                    return False
            return len(stack) == 0
    

  • 0
    H

    @nirnaor why do you need to check len(stack) == 0 in the elif?


  • 0
    N

    @HammerKing Notice that you'll get to the elif part only when char is a close parantheses. Consider these two inputs that should return False:

    1. s =='(]' : Returns False because pairs[stack.pop()] is ')' which is not ']'.
    2. s ==']' : Returns False because no matching parantheses was inserted earlier to the stack, thus len(stack) == 0.

    Without the first part, stack.pop would have raised an IndexError.


Log in to reply
 

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