유효한 괄호 LeetCode 솔루션

난이도 쉽게
자주 묻는 질문 어도비 벽돌 아마존 Apple 눈보라 블룸버그 게시물에서 ByteDance Expedia Facebook 골드만 삭스 구글 IBM 리프트 Microsoft 신탁 스포티 파이 Zillow
버퍼링된 출력 스트림 조회수 196

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

In 유효한 괄호 우리가 준 LeetCode 문제 '(', ')', '{', '}', '[' 및 ']' 문자만 포함하는 경우 입력 문자열이 유효한지 확인합니다. 여기에서 유효한 괄호 LeetCode 솔루션을 제공합니다.

입력 문자열은 다음과 같은 경우에 유효합니다.

  1. 열린 브래킷은 동일한 유형의 브래킷으로 닫아야합니다.
    • ()
    • []
    • {}
  2. 열린 괄호는 올바른 순서로 닫아야합니다.
    • ()][ 유효하지
    • () {[]} 유효
    • [() {}] 유효

입력: str =“[] {() ()}”

산출: 주어진 문자열에 유효한 괄호가 포함되어 있습니다.

유효한 괄호에 대한 알고리즘

n : 문자열 길이

str : 입력 문자열

  1. 스택 S를 선언하고 초기화합니다.
  2. i에서 0에서 n까지 루프를 실행합니다.
    1. str [i]가 여는 괄호이면 스택에서 str [i]를 누릅니다.
    2. str [i]가 닫는 대괄호이면 두 가지 가능성이 있습니다.
      • 스택에있는 상단 브래킷이 동일한 유형의 여는 브래킷 인 경우 스택의 상단 요소를 팝합니다.
      • 그렇지 않으면 false를 반환합니다.
  3. S.empty ()를 반환합니다.

단계별 작업 프로세스

str = [{} ()]

N = 6

1 단계 : 여는 대괄호 [를 얻습니다. 따라서 [를 스택에 밀어 넣습니다.

2 단계 : 여는 대괄호 {를 얻습니다. 따라서 스택에 {를 누릅니다.

유효한 괄호 LeetCode 솔루션

3 단계 : 닫는 대괄호}와 상단 스택 {이므로 스택에서 팝 작업을 수행합니다.

유효한 괄호

 

4 단계 : 우리는 여는 대괄호를 얻습니다 (따라서 스택에서 ().

5 단계 : 닫는 대괄호가 표시되고 스택의 맨 위는 (이므로 스택에서 팝 작업을 수행합니다.

 

유효한 괄호
유효한 괄호

6 단계 : 닫는 대괄호]를 얻고 스택의 맨 위는 [이므로 스택에서 팝 연산을 수행합니다.

유효한 괄호 LeetCode 솔루션

유효한 괄호에 대한 구현 LeetCode 솔루션

유효한 괄호를위한 C ++ 프로그램

#include<bits/stdc++.h>
using namespace std;
bool isValid(string s) {
    stack<char> bracket;
    for (char& c : s) {
        switch (c) {
            case '(': bracket.push(c); break;
            case '{': bracket.push(c); break;
            case '[': bracket.push(c); break;
            case ')': if (bracket.empty() || bracket.top()!='(') return false; else bracket.pop(); break;
            case '}': if (bracket.empty() || bracket.top()!='{') return false; else bracket.pop(); break;
            case ']': if (bracket.empty() || bracket.top()!='[') return false; else bracket.pop(); break;
            default: ; 
        }
    }
    return bracket.empty() ;
}
int main(){
    string s = "[[]{}]()";
    bool check = isValid(s);
    if(check){
        cout<<"The given string contains valid parentheses.";
    }
    else{
        cout<<"The given string contains invalid parentheses.";
    }
}
The given string contains valid parentheses.

유효한 괄호를위한 JAVA 프로그램

import java.util.*; 
public class Main
{
    public static boolean isValid(String s) {
        Stack<Character> bracket = new Stack<>();
        for (char c : s.toCharArray()) {
             switch (c) {
                case '(': bracket.push(c); break;
                case '{': bracket.push(c); break;
                case '[': bracket.push(c); break;
                case ')': if (bracket.empty() || bracket.peek()!='(') return false; else bracket.pop(); break;
                case '}': if (bracket.empty() || bracket.peek()!='{') return false; else bracket.pop(); break;
                case ']': if (bracket.empty() || bracket.peek()!='[') return false; else bracket.pop(); break;
                default: ; 
            }
        }
        return bracket.isEmpty();
    }
  public static void main(String[] args) {
      String s = "{}[)(]";
      boolean check = isValid(s);
          if(check){
                System.out.println("The given string contains valid parentheses.");
            }
            else{
                System.out.println("The given string contains invalid parentheses.");
            }
  }
}
The given string contains invalid parentheses.

복잡성

시간 복잡성

O (N)

여기서 n은 주어진 문자열을 한 번 순회 할 때 주어진 문자열의 길이입니다.

스택의 pop (), top () 및 push () 작업에는 일정한 시간이 걸립니다.

공간 복잡성

O (N)

추가 스택 공간을 사용할 수 있고 최악의 경우 스택 크기는 n / 2가 될 수 있습니다.

참조

균열 시스템 설계 인터뷰
Translate »
1