알고리즘 문제 12 의 효과 적 인 괄호

7906 단어 알고리즘괄호 일치창고.
제목.
'(', ')', '{', '}', '[', ']' 만 포함 하 는 문자열 을 지정 하여 문자열 이 올 바른 지 판단 합 니 다.
유효한 문자열 만족:
  • 왼쪽 괄호 는 같은 유형의 오른쪽 괄호 로 닫 아야 한다.
  • 왼쪽 괄호 는 반드시 정확 한 순서 로 닫 아야 한다.
  • 빈 문자열 은 유효한 문자열 로 여 겨 질 수 있 습 니 다.

    • 사고의 방향
  • 이 문 제 는 대학원 수준의 문제 일 것 입 니 다. 대학 1 학년 때 데이터 구 조 를 배 울 때 선생님 께 서 이런 문 제 를 내 셨 던 기억 이 있 습 니 다. 그 당시 에 정말 어리둥절 한 표정 이 었 는데 지금 은 이런 문 제 를 풀 면 아주 가 벼 워 집 니 다.
  • 본질은 스 택 의 선진 적 인 후 출 원 리 를 이용 하 는 것 이다 ① 왼쪽 괄호 를 만 났 을 때 모두 스 택 에 들어간다.② 오른쪽 괄호 를 만 났 을 때 스 택 이 null 인지 여 부 를 먼저 판단 합 니 다. null 이 라면 현재 오른쪽 괄호 가 일치 하지 않 음 을 설명 합 니 다. false ③ 로 돌아 갑 니 다. 스 택 이 null 이 아니라면 스 택 꼭대기 가 현재 오른쪽 괄호 와 일치 하 는 지 판단 합 니 다. 팝 업 스 택 꼭대기 와 일치 하지 않 으 면 전체 문자열 이 유효한 괄호 가 아 닌 false 로 돌아 갑 니 다.④, 스 택 을 옮 겨 다 닐 때 null 이 어야 합 니 다. null 이 아니라면 왼쪽 괄호 가 일치 하지 않 았 음 을 설명 하고 false
    • 로 돌아 갑 니 다.
    코드 를 첨부 하 다
    public boolean isValid(String s) {
     
    Stack<Character> stack = new Stack<>();
    char[] chars = s.toCharArray();
    for (int i = 0; i < chars.length; i++) {
     
        char aChar = chars[i];
        if (aChar == '(' || aChar == '{' || aChar == '[') {
     
            stack.add(aChar);
        }
        if(stack.isEmpty()){
     
            return false;
        }
        if(aChar == ')'){
     
            if(stack.peek() != '('){
     
                return false;
            }
            stack.pop();
        } else if(aChar == '}'){
     
            if(stack.peek() != '{'){
     
                return false;
            }
            stack.pop();
        } else if(aChar == ']'){
     
            if(stack.peek() != '['){
     
                return false;
            }
            stack.pop();
        }
    }
    return stack.isEmpty();
}
    단순 산 목록 예제 와 간단 한 DFS 예제
    [leetcode] 교 체 된 최 장 중복 문자 (슬라이딩 창)

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage