자바스크립트 인터뷰 코딩 테스트 문제 4

균형 브래킷
괄호의 균형 여부를 확인하는 방법을 알아보세요. 이것은 소프트웨어 개발자가 때때로 해결해야 하는 실제 문제이며 많은 개발 도구에는 자체 구현이 있습니다. 코드 편집기가 우리의 실수를 선택하고 일치하지 않는 대괄호를 정확히 강조 표시하는 방법을 배우게 됩니다.
균형 브래킷
지침
문자열이 주어졌을 때 균형 잡힌 괄호() 중괄호() 및 대괄호[]가 모두 포함되어 있으면 true를 반환합니다.
입력: 문자열
출력: 부울
예
is8alanced("(x + y) - (4)”);//-> 참 is8alanced("(((10 ) (}) ((?)(:)))”);//-› 참 isBalanced( "[{()}]”);//-› 참 is8alanced("(50)(”);//-> 거짓
isBalanced("[{]}”);//-› 거짓

1   funct1on 1sBa1anced(str) {
2   //  Your code here
        }

해결책

2   const openstack = [];
3   const open = '([{';
4   const close = ')]}';
5   const matches - {
6   ')': '(',
7   ']': '[',
8   '}': '{'
9   };
10
11  for (let i - 0; i ‹ str.length; i++) (
12  const char str[i]; 13
14  // If it's an open bracket, push it into our array
15  if(open.includes(char)) (   
16    openstack.push(char); 
17          
18    // If it's a close bracket    
19    } else if(close.includes(char)) ( 
20      // pop an item from the open brackets array.    
21      const lastopenBracket   openStack.pop();    
22          
23      // If the open and close bracket don't match,    
            return false
24      if(matches[char] !== lastopenBracket) { 
25        return false; 
26      }   
27      
28
30  // Ensures there are no characters left on the stack    
31  return !openStack.length;

작동 방식
for 루프에서는 모든 문자를 처리합니다. 현재 문자가 여는 괄호이면 openstack 배열에 푸시합니다.
괄호가 아니면 아무것도 하지 않습니다.
문자열 처리가 완료되면 문자열이 있는지 확인해야 합니다.
스택에 남아 있는 열린 괄호가 없습니다. 있는 경우 문자열의 균형이 맞지 않습니다.
시간
이것은 시간 복잡도 Df가 있는 솔루션입니다.
0(엔)
우주
공간 복잡도는 다음과 같습니다.
0(엔)
문자는 일반적으로 입력 크기에 비례하는 배열에 저장됩니다.
결론
이 고양이의 가죽을 벗기는 방법에는 여러 가지가 있습니다. 또 다른 해결책은 중간으로 이동하면서 처음과 끝에 하나씩 두 개의 포인터를 갖는 것이었습니다. 그들은 그들이 만날 때까지 괄호가 일치하는지 확인하기 위해 확인할 것입니다. 이것은 또한 o(n) 솔루션이 될 것입니다.