매일 한 문제 (센 슨 학 전단 의 괄호 일치 문제 열기)

머리말
안녕하세요, 저 는 금 을 파 는 데 3 개 월 이 넘 게 머 물 렀 습 니 다. 전단 의 사내 들 의 발걸음 이 매우 가지런 하 다 고 생각 하여 매일 한 문제 씩 자신의 성장 궤적 을 기록 하기 로 결 정 했 습 니 다.
우리 가 오늘 볼 것 은 간단 한 데이터 구조 응용 문제 이다.
제목 요구
(), {}, [] 만 포함 하 는 문자열 을 지정 하여 괄호 일치 (닫 기) 가 합 법 적 인지 판단 합 니 다.
유효한 괄호 는 왼쪽 괄호 를 만족 시 키 려 면 반드시 같은 유형의 오른쪽 괄호 로 닫 아야 한다. 왼쪽 괄호 는 반드시 정확 한 순서 로 닫 아야 한다.
예시:
입력: "()[]{}" 출력 true입력: "([)]" 출력 false입력: ")(()))" 출력 false입력: "()" 출력 true입력: "((([])))" 출력 true입력: "]][[" 출력 false입력: ([)] 출력 false여기 서 여러분 에 게 이렇게 많은 예 를 드 리 는 이 유 는 여러분 이 처음에 이 문제 의 의 도 를 이해 하 게 하기 위해 서 입 니 다!
자, 우리 전단 으로 엔지니어 의 뇌 세 포 를 개발 하면 이 문 제 를 이해 하기에 충분 하 다 고 믿 습 니 다. ， ， ！ ！
해법 분석
우 리 는 위의 예 를 가지 고 와 서 분석 할 수 있다. 만약 우리 가 첫 번 째 로 본다 면.
입력: "()[]{}" 출력 true우 리 는 위의 이런 상황 을 똑똑히 볼 수 있다.
첫 번 째 작은 괄호 는 왼쪽 괄호 이 고 두 번 째 작은 괄호 는 오른쪽 괄호 이기 때문에 그들 은 이미 성공 (합 법) 과 일치 했다. 그러면 다시 뒤 를 돌아 보면 세 번 째 중 괄호 는 왼쪽 괄호 이 고 네 번 째 작은 괄호 는 오른쪽 괄호 이기 때문에 그들 도 성공 했다. 다시 뒤 를 돌아 보면 다섯 번 째 괄호 는 왼쪽 괄호 이 고 여섯 번 째 괄호 는 오른쪽 괄호 이기 때문에 성공 했다.마지막 에 그들 은 모두 일치 해서 돌 아 왔 다 true.
이번 에는 우리 반 례 를 찾 아 분석 해 보 자
입력: ")(()))" 출력 false입력: "]][[" 출력 false우리 다시 위의 이런 반 례 상황 을 보 자.
괄호 는 처음에 오른쪽 괄호 였 다. 그러면 이런 상황 이 발생 하면 우 리 는 이것 이 불법 이 라 고 직접 판단 할 수 있다. 왜냐하면 그의 뒤에 그 와 일치 하 는 괄호 가 더 이상 있 을 수 없 기 때문이다.
사실 위의 이런 상황 이 바로 이 문제 의 경계 상황 이다.
그러면 위 에서 우 리 는 이렇게 많은 것 을 분 석 했 으 니 바로 코드 를 올 려 라!
카운터 해법

function valid(str) {
  let small = 0, big = 0, brace = 0; //small    big    brace   
  for (let i = 0; i < str.length; i++) {
    if (str[i] === '(') small++;
    if (str[i] === ')') small--;
    if (str[i] === '[') big++;
    if (str[i] === ']') big--;
    if (str[i] === '{') brace++;
    if (str[i] === '}') brace--;
    if (small < 0 || big < 0 || brace < 0) return false;
  }
  return small === 0 && big === 0 && brace === 0;
}
let isValid = valid("(())")//true
let isValid = valid("()[]{}")//true
let isValid = valid("]][[")//false
let isValid = valid("([)]")//true

우 리 는 이 코드 가 어떤 방향 으로 해결 되 었 는 지 살 펴 보 자. 우 리 는 그 가 계수 법 을 사용 하여 모든 괄호 에 각각 계산 기 를 정 해 주 었 는 지 빨리 알 수 있 을 것 이다. 왼쪽 괄호 를 만나면 1 을 더 하고 오른쪽 괄호 를 만나면 1 을 줄 일 수 있다. 만약 에 마지막 에 그들의 계수 기 는 0 설명 이 모두 상쇄 된다 면 그것 은 합 법 적 인 것 이다.처음에 오른쪽 괄호 였 던 상황 도 고려 했 습 니 다. 순환 이 끝 날 때마다 마이너스 가 하나 있 으 면 처음에 오른쪽 괄호 였 던 상황 을 만 나 false (괄호 가 일치 하지 않 음) 로 돌아 가 는 것 을 의미 합 니 다.
그러나 자세 한 독 자 는 이미 실 마 리 를 발견 했다. 글 의 시작 예 에서 입력: ([)] 출력 false 이지 만 상기 코드 를 사용 한 후에 결 과 를 true 로 되 돌려 주 었 다.
여러분 자세히 생각해 보 세 요. 사실 여기 괄호 의 상대 적 인 위 치 는 매우 중요 합 니 다.만약 우리 가 여기에서 계수 기 를 유지 하고 있다 면, 우리 가 닫 힌 작은 괄호 를 만 나 기만 한다 면, 우 리 는 여기에 사용 할 수 있 는 짝 짓 기 되 지 않 은 개 구 부 괄호 가 있다 는 것 을 알 게 될 것 이다.그러나 최근 의 짝 짓 기 되 지 않 은 괄호 는 닫 힌 작은 괄호 가 아니 라 사각형 괄호 이기 때문에 계산 방법 은 여기 서 깨 졌 다.
게다가 우 리 는 먼저 결과 가 어떠한 지 보지 않 고 그의 알고리즘 복잡 도 를 분석 해 보 자.
우리 가 봤 어.

for (let i = 0; i < str.length; i++) {
    if (str[i] === '(') small++;
    if (str[i] === ')') small--;
    if (str[i] === '[') big++;
    if (str[i] === ']') big--;
    if (str[i] === '{') brace++;
    if (str[i] === '}') brace--;
}

문자열 길이 가 변 할 수 있 는 문자열 이 들 어 왔 습 니 다.
우 리 는 큰 O 표현 법 을 사용 합 니 다. 만약 에 한 문제 의 규모 가 n 이 라면 이 문 제 를 푸 는 특정한 알고리즘 에 필요 한 시간 은 T (n) 이 고 T (n) 는 이 알고리즘 의 '시간 복잡 도' 라 고 부 릅 니 다.
그러면 우 리 는 이 코드 에 for 순환 이 있 고 str. length 는 알 수 없 는 n 으로 볼 수 있다. 순환 체 중의 코드 는 n (str. length) 회 를 실행 해 야 하기 때문에 우 리 는 이런 시간 복잡 도 를 선형 단계 O (n) 라 고 부른다.
주의: 시간 복잡 도 는 프로그램의 구체 적 인 시간 소 모 를 계산 하 는 데 쓰 이 는 것 이 아 닙 니 다.
그렇다면 그의 공간 복잡 도 는?
시간 복잡 도 는 프로그램의 구체 적 인 시간 을 계산 하 는 데 쓰 이 는 것 이 아니 므 로 우 리 는 공간 복잡 도 는 프로그램 이 실제 차지 하 는 공간 을 계산 하 는 데 쓰 이 는 것 이 아니 라 는 것 을 알 아야 한다.공간 복잡 도 는 하나의 알고리즘 이 실행 과정 에서 저장 공간 크기 를 임시로 차지 하 는 양 이다. 똑 같이 하나의 추 세 를 나타 내 고 우 리 는 S (n) 로 정의 한다.
이 세 개의 변 수 는 n (str. length 의 증가 에 따라 다른 변 수 를 만 들 지 않 기 때문에 이곳 의 임시 공간 은 n 의 증가 에 따라 증가 하지 않 는 다. 즉, S (n) = O (1) 이다.
정규 해법

function valid(str) {
  let length;
  do{
    length = str.length;
    str = str.replace("()","").replace("{}","").replace("[]","");
  }while(length != str.length);
  return str.length == 0
}
let isValid = valid("(())")//true
let isValid = valid("()[]{}")//true
let isValid = valid("]][[")//false
let isValid = valid("([)]")//false

이번 수출 결 과 는 모두 우리 가 원 하 는 것 임 을 알 수 있 습 니 다. 그러면 이 해법 은 어떤 생각 입 니까? 사실은 매우 간단 합 니 다. 가장 관건 적 인 논 리 는 replace 라 는 문장 입 니 다. 만약 에 그 가 좌우 에 일치 하 는 괄호 가 있다 면 그 를 빈 것 으로 바 꾼 다음 에 이 조작 을 반복 하 는 것 입 니 다. 마지막 에 그 가 비어 있다 는 것 은 그 가 일치 하 는 것 을 설명 하 는 것 입 니 다. 여기 서 그의 시간 복잡 도 는 판단 하기 어렵 습 니 다.단, 그의 시간 복잡 도 는 평균 상황 에서 2 분 의 n 제곱 의 이런 시간 복잡 도 에 이 를 것 이다. 그러면 그의 공간 복잡 도 는 역시 O (1) 이다.
스 택 (데이터 구조) 해법
js 에서 우 리 는 배열 을 통 해 스 택 데이터 구 조 를 모 의 할 수 있다 는 것 을 잘 알 고 있 을 것 이다.
여기 서 먼저 아 이 디 어 를 제공 합 니 다.
왼쪽 괄호 는 틀림없이 합 법 적 인 것 이다. 다만 우 리 는 그 가 다음 에 오른쪽 괄호 가 그 와 일치 하 는 지 를 봐 야 한다. 그래서 왼쪽 괄호 에 대해 우 리 는 잠시 판단 할 수 없 기 때문에 우 리 는 그것 을 저장 하 는 것 이다. 즉, 스 택 (push) 이다.
오른쪽 괄호 라면 오른쪽 괄호 는 독립 적 으로 존재 할 수 없습니다. 오른쪽 괄호 는 왼쪽 괄호 와 일치 해 야 합 니 다. 그래서 우 리 는 (peek) 스 택 꼭대기 에 그것 과 일치 하 는 괄호 가 있 는 지 확인 해 야 합 니 다. 오른쪽 작은 괄호 라면 왼쪽 작은 괄호 를 찾 아야 합 니 다. 다른 것 은 이런 식 으로 유추 합 니 다. 일치 하면 스 택 꼭대기 요 소 를 내 놓 습 니 다 (pop)., 일치 하지 않 으 면 설명 뒤에 더 이상 할 필요 가 없 으 므 로 false 로 돌아 갑 니 다 (일치 하지 않 음)
전체 절 차 를 다 걸 을 수 있 고 일일이 일치 하면 이 스 택 자체 가 비어 있 을 것 입 니 다.
우 리 는 예시 하 나 를 가지 고 와 서 도시 설명 (){} 을 했다. 처음에 우리 의 스 택 은 이 랬 다.
막 들 어 왔 는데, 우 리 는 왼쪽 작은 괄호 를 창고 에 넣 었 다. 그림 과 같다.
이어서 가다가 오른쪽 작은 괄호 를 발 견 했 습 니 다. 창고 꼭대기 가 지금 왼쪽 작은 괄호 이기 때문에 그들 두 사람 이 일치 하 는 데 성 공 했 습 니 다. 그래서 왼쪽 작은 괄호 를 창고 에서 꺼 낸 후에 창고 가 이렇게 되 었 습 니 다.
이어서 왼쪽 괄호 를 만 나 창고 에 넣 었 다.
이어서 가다가 오른쪽 괄호 를 발 견 했 습 니 다. 창고 꼭대기 가 지금 왼쪽 괄호 이기 때문에 그들 두 사람 이 일치 하 는 데 성 공 했 습 니 다. 그래서 왼쪽 괄호 를 창고 에서 꺼 낸 후에 창고 가 이렇게 되 었 습 니 다.
전체 문자열 도 옮 겨 다 녔 습 니 다. 스 택 이 비어 있 기 때문에 이 괄호 는 합 법 적 입 니 다!
다른 예 는 여러분 이 한번 해 보 셔 도 됩 니 다.
이제 시간 복잡 도 를 분석 할 시간 이 왔 습 니 다.
모든 요소 가 스 택 에 들 어가 고 스 택 에 나 가 는 시간 복잡 도 는 O (1) 의 시간 복잡 도 임 을 알 수 있 습 니 다. 그 다음 에 모든 요 소 는 스 택 에 한 번 들 어가 고 한 번 만 들 어가 기 때문에 마지막 으로 O (1) * n = > O (n) 의 시간 복잡 도 입 니 다. 시간 복잡 도 는 가장 큰 시간 복잡 도 를 가 져 야 하기 때 문 입 니 다.
공간 복잡 도: 최 악의 경우: 모든 요소 가 이 스 택 에 눌 려 있 기 때문에 O (n) 의 공간 복잡 도 입 니 다.
다음은 실현 코드.

function valid(str) {
  let stack = [];
  let paren_map = {')': '(', ']': '[', '}': '{'};
  for (let i = 0, len = str.length; i < len; i++) {
    let tmpStr = str.charAt(i);
    if (!(tmpStr in paren_map)) {
      stack.push(tmpStr);
    } else if (stack.length !== 0 && paren_map[tmpStr] !== stack.pop()) {
      return false;
    }
  }
  return stack.length === 0;
}
let isValid = valid("(())")//true
let isValid = valid("()[]{}")//true
let isValid = valid("]][[")//false
let isValid = valid("([)]")//false

if (!(tmpStr in paren_map)) 이 말 은 만약 에 현재 옮 겨 다 니 는 괄호 가 그 가 정의 한 map 에 없다 면 그 는 오른쪽 괄호 가 아니 라 왼쪽 괄호 이다. 왼쪽 괄호 라면 우 리 는 stack 에 넣 고 그렇지 않 으 면 오른쪽 괄호 라 는 것 을 설명 하기 때문에 우 리 는 스 택 꼭대기 의 요소 와 비교 하여 일치 하 는 지 를 보 자 는 것 이다. stack.length === 0이 문장 은 창고 에 원소 가 있 는 지 판단 하 는 것 이다. 만약 에 원소 가 있다 면 창고 꼭대기 stack.pop() 가 처음에 저 장 된 paren_map[tmpStr] 와 일치 하 는 지, 일치 하지 않 으 면 false (비합법적) 로 바로 돌아 가 고, 일치 하지 않 으 면 창고 가 비어 있 는 지 판단 해 야 한다 return stack.length === 0. 창고 가 비어 있 으 면 설명 은 합법적이다.
이 논 리 는 비교적 추상 적일 수 있 으 니, 모두 debug 에 가면 알 수 있 습 니 다!
총결산
우 리 는 위의 문 제 를 풀 어 여러 가지 해법 을 찾 아 냈 습 니 다. 물론 여러 가지 해법 이 있 을 것 이 라 고 믿 습 니 다. 그러나 우리 의 목 표 는 이 문 제 를 해결 하면 되 는 것 이 아니 라 성능 이 가장 좋 은 것 을 써 야 합 니 다. 간단 한 상용 알고리즘 은 우리 전단 에서 도 매우 중요 합 니 다. 평소에 여러분 들 은 이런 문 제 를 많이 해결 할 수 있 습 니 다.
사내 들 이 글 속 의 잘못 을 발견 하면 평론 가 에서 지적 해 주세요. 제 가 제때에 수정 하 겠 습 니 다! ， ！