[stack] valid parentheses

✅ Problem

https://leetcode.com/problems/valid-parentheses/description/

 

✅ Approach & Solution

방식1) Deque 인터페이스 사용한 Stack 구현

플로우

• (, {, [ : stack push
• ), }, ] : stack pop
  • 빈 스택인 경우 : not valid
  • 대응하는 open bracket이 아닌 경우 : not valid
• 빈 스택이 아닌 경우 : not valid

class Solution {
    public boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();

        boolean result = true;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) {
                    result = false;
                    break;
                }

                char top = stack.pop();
                if (c == ')' && top != '(' ||
                    c == '}' && top != '{' ||
                    c == ']' && top != '[') {
                    result = false;
                    break;
                }
            }
        }
        
        if (!stack.isEmpty()) {
            result = false;
        }

        return result;
    }
}

 

방식2) Array 사용한 Stack 구현

배열로만 처리한다면?

• 시작 index = -1
  • index == -1 이면, 빈 스택
• open bracket인 경우 대응하는 close bracket을 배열에 저장
• close bracket인 경우 배열에 존재하는 값이 본인과 일치하면 valid, 일치하지 않으면 not valid

class Solution {
    public boolean isValid(String s) {
        int top = -1;
        char[] bracketArr = new char[s.length()];

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

            if (c == '(') {
                bracketArr[++top] = ')';
            } else if (c == '{') {
                bracketArr[++top] = '}';
            } else if (c == '[') {
                bracketArr[++top] = ']';
            } else {
                if (top == -1) {
                    return false;
                } else {
                    if (bracketArr[top--] != c) {
                        return false;
                    }
                }
            }
        }

        return top == -1; // if stack is not emtpy, not valid
    }
}