식에서 주어진 여는 괄호에 대한 닫는 괄호 색인 찾기


난이도 쉽게
자주 묻는 질문 어도비 벽돌 아마존 Flipkart 신탁 오요 룸 스냅 딜 월마트 연구소 야 트라
배열 스택

문제 정책

주어진 길이 / 크기 n의 s 및 여는 대괄호의 인덱스를 나타내는 정수 값. 식에서 주어진 여는 대괄호에 대한 닫는 대괄호의 색인을 찾습니다.

식에서 주어진 여는 괄호에 대한 닫는 괄호 색인 찾기

s = "[ABC[23]][89]"

index = 0
8
s = "[C-[D]]"

index = 3
5
s = "E-[FX]]"

index = 0
-1

접근

사용하십시오 스택 데이터 구조 정수 주어진 문자열에서 여는 괄호의 인덱스를 저장하려면 type. 주어진 반복 시작 주어진 색인에서 시작합니다. 여는 괄호가 발견되면 스택에 밀어 넣습니다. 접하는 모든 닫는 대괄호에 대해 스택에서 여는 대괄호를 꺼냅니다. 스택이 비어있는 경우, 즉 스택의 크기가 일부 인덱스에서 0이면 인덱스를 인쇄합니다. 그렇지 않으면 -1을 인쇄하십시오.

암호알고리즘

  1. 길이 / 크기의 문자열 초기화 n 및 여는 대괄호의 인덱스를 나타내는 정수 값.
  2. 표현식을 나타내는 문자열 값과 주어진 문자열에서 여는 괄호의 인덱스를 나타내는 정수 값을 매개 변수로 받아들이는 주어진 문자열에서 주어진 여는 괄호에 대한 닫는 괄호의 인덱스를 찾는 함수를 만듭니다.
  3. 주어진 색인에있는 문자가 여는 괄호와 같지 않은지 확인하십시오. 즉 '[', -1을 인쇄하고 리턴하십시오.
  4. 그 후 정수 유형의 스택 데이터 구조를 생성하여 주어진 문자열의 여는 괄호 인덱스를 저장합니다.
  5. 주어진 색인에서 시작하여 주어진 문자열을 순회하고 문자열의 현재 색인에있는 문자가 여는 대괄호와 같은지 확인하고 스택의 문자열에서 현재 색인에있는 문자를 푸시 / 삽입합니다.
  6. 그렇지 않으면 문자열의 현재 색인에있는 문자가 닫는 대괄호, 즉 ']'와 같으면 스택 맨 위에있는 요소를 팝 / 제거합니다. 그 후 스택이 비어 있는지 확인합니다. 즉, 스택의 크기가 0과 같은지 확인하고 현재 인덱스를 인쇄하고 반환합니다.
  7. 인쇄 -1.

암호

여는 대괄호에 해당하는 닫는 대괄호를 찾는 C ++ 프로그램

#include <bits/stdc++.h> 
using namespace std; 
  
void test(string expression, int index){ 
    int i; 
      
    if(expression[index]!='['){ 
        cout << "-1\n"; 
        return; 
    } 
      
    stack <int> st; 
      
    for(i = index; i < expression.length(); i++){ 
          
        if(expression[i] == '['){ 
            st.push(expression[i]);
        }
          
        else if(expression[i] == ']'){ 
            st.pop(); 
            if(st.empty()){ 
                cout << i << "\n"; 
                return; 
            } 
        } 
    } 
      
    cout << "-1\n"; 
} 
  
int main() { 
    string s = "[ABC[23]][89]";
    int index = 0;
    
    test(s, index); 
    
    return 0; 
}
8

여는 대괄호에 해당하는 닫는 대괄호를 찾는 Java 프로그램

import java.util.Stack; 

class FindIndex{ 
  
    static void test(String expression, int index){ 
        int i; 
  
        if(expression.charAt(index) != '['){ 
            System.out.print("-1\n"); 
            return; 
        } 
  
        Stack<Integer> st = new Stack<>(); 
  
        for(i = index; i < expression.length(); i++){ 
  
            if(expression.charAt(i) == '['){ 
                st.push((int) expression.charAt(i)); 
            } 
            
            else if(expression.charAt(i) == ']'){ 
                st.pop(); 
                if(st.empty()){ 
                    System.out.print( i ); 
                    return; 
                } 
            } 
        } 
  
        System.out.print("-1\n"); 
    } 
  
    public static void main(String[] args){
        String s = "[ABC[23]][89]";
        int index = 0;
        
        test(s, index); 
    } 
}
8

복잡성 분석

시간 복잡성

O (n) 여기서 n은 주어진 문자열 s의 길이입니다. 문자열에서 사용 가능한 모든 문자를 순회했기 때문에 시간 복잡도는 선형입니다.

공간 복잡성

O (n) 주어진 문자열의 문자를 저장하기 위해 공백을 사용했기 때문입니다. 공간 복잡성은 브래킷 수에 따라 다릅니다. 그러나 최악의 경우 모든 문자가 대괄호 일 수 있습니다. 따라서 공간 복잡성도 선형입니다.

참조