20. Valid Parentheses.md

20. Valid Parentheses

---

leetcode-cn Daily Challenge on August 14th, 2020.

leetcode Daily Challenge on January 20th, 2021.

---

Difficulty : Easy

Related Topics : String、Stack

---

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.

Example 1:

Input: "()"
Output: true

Example 2:

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

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true

---

Solution

• mine
  • Java
    • Runtime: 1 ms, faster than 98.63%, Memory Usage: 34.3 MB, less than 100.00% of Java online submissions

      // O(N)time
      // O(N)space
      public boolean isValid(String s) {
          if (s == null || s.length() == 0) {
              return true;
          }
          char[] array = s.toCharArray();
          Stack<Character> stack = new Stack<>();
          for (char c : array) {
              if (c == '{' || c == '[' || c == '(') {
                  stack.push(c);
              } else {
                  if (stack.size() == 0) {
                      return false;
                  }
                  char t = stack.pop();
                  if (!(c == ']' && t == '[')
                          && !(c == ')' && t == '(')
                          && !(c == '}' && t == '{')) {
                      stack.push(t);
                      stack.push(c);
                  }
              }
          }
          return stack.size() == 0;
      }
      

---

• the most votes

• Runtime: 1 ms, faster than 98.67%, Memory Usage: 37.5 MB, less than 5.06% of Java online submissions

  // O(N)time
  // O(N)space
  public boolean isValid(String s) {
    Stack<Character> stack = new Stack<Character>();
    for (char c : s.toCharArray()) {
        if (c == '(')
            stack.push(')');
        else if (c == '{')
            stack.push('}');
        else if (c == '[')
            stack.push(']');
        else if (stack.isEmpty() || stack.pop() != c)
            return false;
    }
    return stack.isEmpty();
  }
  

---