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

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

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      

29          
30      // Ensures there are no characters left on the stack    
31      return !openStack.length;   
32  }       

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