[LeetCode] 20 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.

Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

Example 4:

Input: s = "([)]"
Output: false

Example 5:

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

Constraints:

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

---

풀이

(, ), {, }, [, ] 가 입력될 때 올바른 괄호쌍이 들어왔는지 확인하는 문제다.
괄호들을 문자가 아닌 아스키코드로 바꾸어 문제를 풀었다.

• 아스키코드
  (: 40, ): 41, {: 123, }: 125, [: 91, ]: 93

• 스택을 이용한다.
  - 여는 괄호면 스택에 넣고,
  - 닫는 괄호면
  - 우선 스택이 비었나 확인한 뒤 비었다면 여는 괄호는 없이 닫는 괄호만 존재하므로 false 를 반환한다.
  - 스택이 비어있지 않다면 스택의 맨 위값과 비교하여 쌍일 경우(두 값의 차가 1이나 2일 때) 지우고, 쌍이 아닐 경우 false 를 반환한다.
  - 입력된 문자열이 다 처리된 후 스택에 남은 괄호가 있다면 false 를 반환한다.
  
  

---

코드

class Solution {
    public boolean isValid(String s) {
        int current;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            current = s.charAt(i);
            if (current == 40 || current == 91 || current == 123) {
                stack.push(current);
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                if (current - stack.peek() == 1 || current - stack.peek() == 2) {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        if (!stack.isEmpty()) {
            return false;
        }
        return true;
    }
}

---

21.07.09 코드

package com.company.w4;

import java.util.Stack;

/*
date: 21.07.09

input: String
output: boolean
constraints: input - (, ), {, }, [, ]
    열린 괄호는 반드시 같은 유형의 괄호로 닫혀야 한다.
    열린 괄호는 반드시 정확한 순서로 닫혀야 한다.
edge cases:
    s.length == 1 -> return false
    s.length % 2 != 0 -> return false

스택에 반만 넣고, 남은 반은 스택에서 하나씩 pop하면서 아스키코드 값의 차이가 1개 또는 2개가
나는지 파악한다.

( : 40 (1 차이)
) : 41
{ : 123 (2 차이)
} : 125
[ : 91 (2 차이)
] : 93

time: O(N), space: O(N)
 */
public class No8 {
    public static void main(String[] args) {
        String s = "{}";
        System.out.println(isValid(s));
    }

    public static boolean isValid(String s) {
        // edge case
        if (s.length() % 2 != 0) return false;

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

        for (int i = 0; i < s.length(); i++) {
            char curBracket = s.charAt(i);
            if (curBracket == '(' || curBracket == '{' || curBracket == '[') {
                stack.push(curBracket);
            } else {
                if(stack.isEmpty()) return false;
                char openBracket = stack.peek();
                stack.pop();
                if (curBracket - openBracket == 1 || curBracket - openBracket == 2)
                    continue;
                else return false;
            }
        }
        if (!stack.isEmpty()) return false;
        return true;
    }
}