유효한 괄호

리트코드 문제: Valid Parentheses

목적:

'(', ')', '{', '}', '[' 및 ']' 문자만 포함하는 문자열 s가 주어지면 입력 문자열이 유효한지 확인합니다.

다음과 같은 경우 입력 문자열이 유효합니다.

열린 괄호는 같은 유형의 괄호로 닫아야 합니다.
여는 괄호는 올바른 순서로 닫아야 합니다.

패턴: 스택

접근하다:

해시맵을 사용하여 짝을 이룬 괄호를 저장합니다: 키 = 닫힌 괄호 및 값 = 열린 괄호.

해시 맵에 현재 문자가 포함되어 있지 않으면 여는 괄호입니다. 스택을 사용하여 열린 괄호를 보관하십시오.

스택이 비어 있는지 확인하면 닫는 괄호가 먼저 추가되지 않습니다. 이 경우 유효하지 않습니다.

스택의 상단을 팝하여 확인하고 상단 문자가 해시맵의 닫는 괄호와 일치하지 않으면 false를 반환합니다.

스택이 비어 있으면 유효한 괄호이므로 true를 반환합니다.

스택이 비어 있지 않으면 false를 반환합니다.

빅오 표기법:

시간 복잡도: O(n)
문자열의 각 문자에 대해 n번 반복합니다.

공간 복잡도: O(n)
저장을 위해 해시 맵 데이터 구조를 사용합니다.

암호:

class Solution {

    public boolean isValid(String s) {
        // use stack to store opening brackets
        Stack <Character> stack = new Stack<>();

        // use a hashmap to store pairs 
        Map <Character, Character> hashMap = new HashMap<>();
        hashMap.put(')','(');
        hashMap.put('}','{');
        hashMap.put(']','[');

        // iterate through s
        // add open brackets to the stack
        // if stack is empty or top char is not a match to c 
        // return false 

        for(char c : s.toCharArray()){
            if(!hashMap.containsKey(c)){
                stack.push(c);
            } else if(stack.isEmpty() || stack.pop() != hashMap.get(c)){
                   return false;
                }
            }
        return stack.isEmpty();        
    }
}