[LeetCode] 20. Valid Parentheses

Problem

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.

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 '()[]{}'.

Solution

Logic

• 문제를 해결하기 위해서는 다음과 같이 문자열 s에서 닫는 괄호가 나왔을 때를 주목해야 한다. ```java
  1. 닫는 괄호가 나왔을 때, 가장 인접한 여는 괄호가 닫는 괄호와 같은 종류여야 한다.

1. 1번에서 사용된 여는 괄호는 다음 계산에서 제외된다. -> 여는 괄호가 선입후출 형식으로 관리되어야 한다.

   - 위의 조건을 만족시키기 위해 자료구조 Stack을 사용한다.
   ## **Code**
   ```java
   class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(' | s.charAt(i) == '[' | s.charAt(i) == '{')
                stack.push(s.charAt(i));
            else {
                if (stack.isEmpty()) return false; // 여는 괄호 없이 닫는 괄호가 온 경우
                else if (s.charAt(i) == ')' && stack.pop() != '(') return false;
                else if (s.charAt(i) == ']' && stack.pop() != '[') return false;
                else if (s.charAt(i) == '}' && stack.pop() != '{') return false;
            }
        } return stack.isEmpty(); // 여는 괄호가 Stack에 남아있는 경우
    }
   }
   

   Time Complexity

   • 문자열 s의 길이를 n이라 가정했을 때, 아래의 반복문은 O(n)의 시간 복잡도를 가진다. 따라서 본 문제는 O(n)의 시간 복잡도를 가진다.

     Stack<Character> stack = new Stack<>();
     for (int i = 0; i < s.length(); i++) {
      if (s.charAt(i) == '(' | s.charAt(i) == '[' | s.charAt(i) == '{')
        stack.push(s.charAt(i));
      else {
        if (stack.isEmpty()) return false; // 여는 괄호 없이 닫는 괄호가 온 경우
        else if (s.charAt(i) == ')' && stack.pop() != '(') return false;
        else if (s.charAt(i) == ']' && stack.pop() != '[') return false;
        else if (s.charAt(i) == '}' && stack.pop() != '{') return false;
      }
     }