[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:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

Example 1

---

• Input: s = “()”
• Output: true

Example 2

---

• Input: s = “()[]{}”
• Output: true

Example 3

---

• Input: s = “(]”
• Output: false

Example 4

---

• Input: s = “([])”
• Output: true

Example 5

---

• Input: s = “([)]”
• Output: false

Constraints

---

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

Hint

---

Hint 1

  Use a stack of characters.
	

Hint 2

  Use a stack of characters.
	

Hint 3

  When you encounter a closing bracket, check if the top of the stack was the opening for it. If yes, pop it from the stack. Otherwise, return false.
	

Code

---

내 제출

---

class Solution {
    public boolean isValid(String s) {
        char[] strs = s.toCharArray();
        int strsLength = strs.length - 1;
        List<Character> temp = new ArrayList<>();
        boolean result = false;

        if (strs[0] == ')' || strs[0] == '}' || strs[0] == ']') { // 첫 문자가 false인 경우
            return false;
        } else if (strs[strsLength] == '{' || strs[strsLength] == '[' || strs[strsLength] == '(') {
            return false;
        }
        for (int i = 0; i < strs.length; i++) {
            //bw.write("strs[i] : " + strs[i] + "\n");
            if (strs[i] == '(' || strs[i] == '{' || strs[i] == '[') {
                switch (strs[i]) {
                    case '(':
                        temp.add(')');
                        break;
                    case '{':
                        temp.add('}');
                        break;
                    case '[':
                        temp.add(']');
                        break;
                }
            } else {
                int tempSize = temp.size() - 1;
                if (tempSize >= 0) {
                    if (strs[i] == temp.get(tempSize)) {
                        //bw.write("true" + "\n");
                        temp.remove(tempSize);
                        result = true;
                    } else {
                        //bw.write("false" + "\n");
                        return false;
                    }
                } else {
                    //bw.write("false" + "\n");
                    return false;
                }
            }
        }
        if (!temp.isEmpty()) {
            return false;
        }
        return result;
    }
}

Runtime	Memory
1 ms	41.8 MB

다른 풀이

---

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;
                }
                if( ch == ')' && stack.peek() != '('){
                    return false;
                }
                if( ch == '}' && stack.peek() != '{'){
                    return false;
                }
                if( ch == ']' && stack.peek() != '['){
                    return false;
                }
                stack.pop();

            } else {
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }
}

Reference

---