The title

Given a string containing only ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘, ‘]’, check whether the string is valid.

A valid string must meet the following requirements:

  • An open parenthesis must be closed with a close parenthesis of the same type.
  • The left parentheses must be closed in the correct order.

Note that an empty string can be considered a valid string.

The sample

Input: "()" output: true input: "() [] {}" output: true input: "[]" output: falseCopy the code

Their thinking

So when we started looking at this problem, we couldn’t help but wonder if we could calculate the number of open parentheses, and the number of close parentheses, if we had the same number of left and right parentheses, would that be valid parentheses?

In fact, no, if the input is [{]}, the left and right parentheses of each type are equal, but not valid parentheses. This is because the result also depends on the position of the parentheses.

Code implementation

def isValid(s):
    dic = {')': '(', ']': '[', '}': '{'}
    stack = []
    for i in s:
        if stack and i in dic:
            if stack[-1] == dic[i]:
                stack.pop()
            else:
                return False
        else:
            stack.append(i)

    return not stack


if __name__ == '__main__':
    print(isValid("()["))
Copy the code