유효한 괄호, Facebook 인터뷰 질문 해결.

이것은 가장 많이 묻는 스크리잉 질문 중 하나이며, 특히 인터뷰가 Hackerrank에서 진행되는 경우 이 질문을 할 가능성이 높습니다. 나는 Hackerrank에서 이와 똑같은 질문을 4번 받았습니다.

질문: '(', ')', '{', '}', '[' 및 ']' 문자만 포함하는 문자열이 주어지면 입력 문자열이 유효한지 확인하십시오.

다음과 같은 경우 입력 문자열이 유효합니다.
열린 괄호는 같은 유형의 괄호로 닫아야 합니다.
여는 괄호는 올바른 순서로 닫아야 합니다.
빈 문자열은 유효한 것으로 간주됩니다.

예:

   string = "()[]{}"              //valid
   string = "[{()]}"              //invalid
   string = ""                    //valid

이것을 해결하자,

최소한 문제는 일치하는 여는 괄호와 닫는 괄호를 찾도록 요청하는 것입니다. 그래서 :
"(", ")"는 유효한 닫는 괄호입니다.
"{", "}"는 유효한 닫는 괄호입니다.
"[", "]"는 유효한 닫는 괄호입니다.

또는 다른 말로, 우리는 "쌍"이 서로 상쇄된다고 말할 수 있습니다. 여기서 우리는 순서가 중요하다고 말할 수 있습니다.

우리에게 도움이 될 좋은 데이터 구조:
1> 괄호를 저장하고 일치하는 항목이 발견되면 취소하고,
2 > 괄호 추적하기

스택입니다. 여는 괄호를 스택에 푸시하고 닫는 괄호를 만나면 팝합니다. 동시에 닫는 괄호가 팝되는 괄호와 유효한 일치인지 확인할 수 있습니다.

구현 - 1

여기서 우리는 문자열이 유효하지 않은 경우에도 길이가 있는지 확인하는 작은 최적화를 만들 수 있습니다.
위의 아이디어를 코드로 변환 :

var isValid = function(S) {
    let stack = [];
    if(S == '') return true;
    if(S%2 != 0) return false;
    for(let s of S){
        if(s == '(' || s == '{' || s == '['){
            stack.push(s);
        }else{
            if(stack.length == 0) return false;
            let c = stack.pop();
            if(c == '(' && s != ')'){
                return false;
            }
            if(c == '{' && s != '}'){
                return false;
            }
            if(c == '[' && s != ']'){
                return false;
            }
        }
    }

    if(stack.length != 0) return false;      // for conditions like "{([])}}}" 
    return true;
};

이제 잘 작동하지만 더 잘할 수 있습니까? "쌍"을 확인하기 위한 if-else 조건이 많이 있습니다. 더 간결하게 만들어 보겠습니다.

구현 - 2

if 조건의 주요 작업은 괄호를 일치시키는 것이므로 다른 데이터 구조인 해시맵을 사용합니다.

닫는 괄호는 해당하는 여는 괄호와 일치해야 하므로 닫는 괄호와 여는 괄호 사이에 매핑을 만듭니다.



따라서 알고리즘은 다음과 같이 작동합니다.
1 > 현재 기호가 해시맵에 있는지 확인하고 그렇지 않은 경우 스택에 푸시합니다.
2 > 현재 기호가 해시맵에 있는 경우 스택에서 팝하고 해시맵 항목에 해당하는 값과 비교합니다.

따라서 현재 기호의 맨 위가 ")"이면 스택에서 팝되고 팝된 값을 "("인 해시맵의 ")"에 해당하는 값과 비교합니다. 동일하지 않으면 문자열이 유효하지 않은 것입니다.

코드는 그것을 훨씬 명확하게 할 것입니다.

var isValid = function(S) {

    if(S == '') return true;
    if(S.length%2 != 0) return false;

    let map = {};
    map[")"] = "(";
    map["}"] = "{";
    map["]"] = "[";

    console.log(map);

    let stack = [];
    for(let s of S){
        if(!map[s]){
            stack.push(s);
        }else{
            if(stack.length == 0) return false;
            let c = stack.pop();
            if(c != map[s]) return false;
        }
    }

    if(stack.length !=0) return false;
    return true;
};

이 문제를 해결하는 더 좋은 방법을 알고 있다면 제 설명이 마음에 드셨기를 바라며 공유해 주세요 :)

github : https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/ValidParentheses.js