[LeetCode] Valid Parentheses 풀이

내 풀이

• 시간복잡도
  • O(N)
• 공간복잡도
  • O(N)

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

        for (char ch : s.toCharArray()) {
            if (ch == ')' || ch == '}' || ch == ']') {
                if (stack.isEmpty()) {
                    return false;
                }

                char peeked = stack.peek();
                if (ch == ')' && peeked == '(') {
                    stack.pop();
                    continue;
                }

                if (ch == '}' && peeked == '{') {
                    stack.pop();
                    continue;
                }

                if (ch == ']' && peeked == '[') {
                    stack.pop();
                    continue;
                }
                return false;
            } else {
                stack.push(ch);
            }
        }

        return stack.isEmpty();
    }
}

최적화

• 시간복잡도
  • O(N)
• 공간복잡도
  • O(N)
• peek을 pop으로 변경하여 중복 호출을 줄였다.

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

        for (char ch : s.toCharArray()) {
            switch (ch) {
                case ')':
                    if (stack.isEmpty() || stack.pop() != '(') return false;
                    break;
                case '}':
                    if (stack.isEmpty() || stack.pop() != '{') return false;
                    break;
                case ']':
                    if (stack.isEmpty() || stack.pop() != '[') return false;
                    break;
                default:
                    stack.push(ch);
            }
        }

        return stack.isEmpty();
    }
}