20.Valid Parentheses
===

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

[20. Valid Parentheses](https://leetcode.com/problems/valid-parentheses/description/)

### 題目描述

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^4^
* `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;
}

> [name=Marsgoat][time=Apr 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

> [name=Ron Chen][time=Mon, 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();
    }
}

> [name=Ron Chen][time=Mon, Apr 10, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)