20.Valid Parentheses

tags: `Easy`,`String`,`Stack`

題目描述

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

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.

範例

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

Constraints:

1 <= s.length <= 10⁴
s consists of parentheses only '()[]{}'.

解答

Javascript





















function isValid(s) {
  const stack = [];
  const map = {
    '(': ')',
    '[': ']',
    '{': '}',
  };

  for (const c of s) {
    if (map[c]) {
      stack.push(c);
    } else {
      if (map[stack.pop()] !== c) {
        return false;
      }
    }
  }

  if (stack.length > 0) return false;
  return true;
}

MarsgoatApr 10, 2023

Python

















class Solution:
    def isValid(self, s: str) -> bool:
        stack = []

        for ch in s:
            if ch in (")", "]", "}"):
                if stack:
                    pop = stack.pop()
                    check = pop + ch
                    if check not in ("()", "[]", "{}"):
                        return False
                else:
                    return False
            elif ch in ("(", "[", "{"):
                stack.append(ch)
            
        return not stack

看到學弟上面的 map 就改寫一下














class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        mapping = {")": "(", "}": "{", "]": "["}

        for ch in s:
            if ch in mapping:
                top_element = stack.pop() if stack else '#'
                if mapping[ch] != top_element:
                  return False
            else:
                stack.append(ch)
            
        return not stack

Ron ChenMon, Apr 10, 2023

Java

落落長的 Java 版本























class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>();
        HashMap<Character, Character> mapping = new HashMap<Character, Character>();
        mapping.put(')', '(');
        mapping.put(']', '[');
        mapping.put('}', '{');

        for(Character ch : s.toCharArray()) {
            if(mapping.containsKey(ch)) {
                Character top_element = stack.isEmpty() ? '#' : stack.pop();
                if(top_element != mapping.get(ch)) {
                    return false;
                }
            }
            else {
                stack.push(ch);
            }
        }

        return stack.isEmpty();
    }
}