> For the complete documentation index, see [llms.txt](https://wentao-shao.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://wentao-shao.gitbook.io/leetcode/other/20.valid-parentheses.md).

# 20.Valid-Parentheses

## 20. Valid Parentheses

## 题目地址

<https://leetcode.com/problems/valid-parentheses/>

## 题目描述

```
Given a string 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.
Note that an empty string is also considered valid.
```

## 代码

### Approach 1: Stacks

Complexity analysis:

* Time complexity: O(n)
* Space complexity: O(n)

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

    Stack<Character> stack = new Stack<Character>();

    for (int i = 0; i < s.length(); i++) {
      char c = s.charAt(i);

      if (mappings.containsKey(c)) {
        char topElement = stack.empty() ? '#' : stack.pop();
        if (topElement != mappings.get(c)) return false;
       } else {
          stack.push(c);
      }
    }

    return stack.isEmpty();
  }
}
```