设计 / 思考 / 材料 / 信息

0%

LeetCode | Valid Parentheses (easy level)

发表于 更新于 Valine：

Problem 20: Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

1
2
Input: "()"
Output: true

Example 2:

1
2
Input: "()[]{}"
Output: true

Example 3:

1
2
Input: "(]"
Output: false

Example 4:

1
2
Input: "([)]"
Output: false

Example 5:

1
2
Input: "{[]}"
Output: true

Good solution for efficiency

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []
        left = ['(','{','[']
        right = [')','}',']']
        mapping = dict(zip(right,left))
        for i in range(len(s)):
            if s[i] in mapping:
                if not stack or mapping[s[i]] != stack.pop():
                    return False
            else:
                stack.append(s[i])
        return not stack

left and right are lists. mapping is a dictionary, which combines right and left using dict and zip function. Searching/matching in dictionary would be more efficient than in list.

Pythonic way to express checking:

1
2
3
4
5
if s[i] in mapping:
    if not stack or mapping[s[i]] != stack.pop():
    	return False
else:
	stack.append(s[i])

If s[i] is not ‘)’,’}’,’]’, then stack.append(s[i]); if s[i] is ‘)’,’}’,’]’, then compare it with stack.pop() — the top element in stack. Concise code speeds the execution…

My ugly solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        
        dict1 = {'(':1, '{':2, '[':3}
        dict2 = {')':'(', '}':'{', ']':'['}
        stack = []

        for n in range(len(s)):
            char = s[n]
            if char in dict1:
                stack.append(char)
            elif char in dict2:
                if stack == []:
                    return False
                if dict2[char] == stack[-1]:
                    stack.pop()
                else:
                    return False
            else:
                return False
        return stack == []

Too many “if” checks slow the solution. 

1
2
if stack == []:
	return False

This check above for test case without left brackets:

“]”

1
2
3
4
if dict2[char] == stack[-1]:
	stack.pop()
else:
	return False

This check above for test case in disorder:

“(])”