Пронајдете индекс на држач за затворање за дадена заграда за отворање во израз


Ниво на тешкотија Лесно
Често прашувано во Adobe Амазон Flipkart Oracle Соби OYO Snapdeal Лаборатории Walmart Yatra
Низа Магацинот Стринг

Изјава за проблем

Со оглед на низа s со должина / големина n и цел број што претставува индекс на заграда на отворање. Пронајдете индекс на заградата за затворање за дадена заграда за отворање во израз.

Пронајдете индекс на држач за затворање за дадена заграда за отворање во израз

пример

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

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

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

index = 0
-1

Пристап

Користете магацинот структура на податоци на број напишете за да го зачувате индексот на држачите за отворање во дадената низа. Започнете со повторување преку даденото низа почнувајќи од дадениот индекс. Ако се сретне заграда за отворање, турнете ја во оџакот. За секоја заграда за затворање што се среќава, отворете ја заградата за отворање од оџакот. Ако оџакот стане празен, т.е. големината на оџакот е 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

Јава програма за да ја пронајдете соодветната заграда за затворање за отворот

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) затоа што искористивме простор за складирање на ликовите од дадената низа. Комплексноста на просторот зависи од бројот на загради. Но, во најлош случај, сите карактери можат да бидат загради на квадрат. Така, вселенската комплексност е исто така линеарна.

Референци