LeetCode - 20.Valid Parentheses

 

[Must-do Easy Question] 시리즈

How to effectively use LeetCode to prepare for interviews!! - LeetCode Discuss

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

Valid Parentheses - LeetCode

 

 

---

문제

Given a string 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.

Note that an empty string is also considered valid.

Example 1:

Input: "()" Output: true

Example 2:

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

Example 3:

Input: "(]" Output: false

Example 4:

Input: "([)]" Output: false

Example 5:

Input: "{[]}" Output: true

---

이건 스택을 써야한다. 그리고 쌍을 맞춰주기 위해 해시맵을 사용했다. 

그런데 계속 15번째 코드에서 EmptyStackException 에러가 난다..

import java.util.*;

class Solution {
    public boolean isValid(String s) {
        Stack < Character > stack = new Stack < Character > ();
        HashMap < Character, Character > map = new HashMap < Character, Character > ();
        map.put('{', '}');
        map.put('(', ')');
        map.put('[', ']');

        for (int i = 0; i < s.length(); i++) {
            if (i == 0) {
                stack.push(s.charAt(i));
            } else {
                if (map.get(stack.peek()) == s.charAt(i)) {
                    stack.pop();
                } else {
                    stack.push(s.charAt(i));
                }
            }
        } //end of loop

        if (stack.isEmpty()) {
            return true;
        } else {
            return false;
        }
    }
}

java.util.EmptyStackExceptionjava.util.EmptyStackExceptionemㄱ

rmfot

그래서 stack 이 empty 일 경우 peek를 확인하지 않고 s.charAt(i)를 push 해주는 조건을 추가했다. 

import java.util.*;

class Solution {
    public boolean isValid(String s) {
        Stack < Character > stack = new Stack < Character > ();
        HashMap < Character, Character > map = new HashMap < Character, Character > ();
        map.put('{', '}');
        map.put('(', ')');
        map.put('[', ']');

        for (int i = 0; i < s.length(); i++) {
            if (i == 0) {
                stack.push(s.charAt(i));
            } else {
                if (stack.isEmpty() == true) {
                    stack.push(s.charAt(i));
                } else {
                    if (map.get(stack.peek()) == s.charAt(i)) {
                        stack.pop();
                    } else {
                        stack.push(s.charAt(i));
                    }
                }
            }
        } //end of loop

        if (stack.isEmpty()) {
            return true;
        } else {
            return false;
        }
    }
}

그러자 이번엔  if (map.get(stack.peek()) == s.charAt(i)) 에서 NullPointException이 뜬다.

 

생각해보니 map 에는 닫는 걸 넣어주지 않았다....

그냥 3개면 if 문 써서 간단하게 처리하면되는데 괜히 해시맵 써보고 싶어서 이러다가 삽질을 했다,..

import java.util.*;

class Solution {
    public boolean isValid(String s) {
        Stack < Character > stack = new Stack < Character > ();
    
        for (int i = 0; i < s.length(); i++) {
            if (stack.isEmpty() == true) {
                stack.push(s.charAt(i));
            } else {
                if(stack.peek() == '(' && s.charAt(i) == ')'){
                    stack.pop();
                }else if(stack.peek() == '{' && s.charAt(i) == '}'){
                    stack.pop();
                }else if(stack.peek() == '[' && s.charAt(i) == ']'){
                    stack.pop();
                }else{
                    stack.push(s.charAt(i));
                }
            }//end of else
        } //end of loop
         System.out.println("");
        System.out.println(stack);

        if (stack.isEmpty()) {
            return true;
        } else {
            return false;
        }
    }
}

통과~~

 

 

다른 사람의 코드를 보자

public boolean isValid(String s) {
	Stack<Character> stack = new Stack<Character>();
	for (char c : s.toCharArray()) {
		if (c == '(')
			stack.push(')');
		else if (c == '{')
			stack.push('}');
		else if (c == '[')
			stack.push(']');
		else if (stack.isEmpty() || stack.pop() != c)
			return false;
	}
	return stack.isEmpty();
}

깔끔하다.. 나도 for문을 iterator를 쓰는걸 연습해야겠다.

Stack<Character>를 쓰는건 국룰인 것 같다.