Намерете индекс на затваряща скоба за дадена отваряща скоба в израз


Ниво на трудност Лесно
Често задавани в Кирпич Амазонка Flipkart Оракул OYO Стаи Snapdeal Walmart Labs Yatra
Array Стек Низ

Декларация за проблема

Като се има предвид a низ s дължина / размер n и цяло число, представляващо индекса на отваряща квадратна скоба. Намерете индекс на затваряща скоба за дадена отваряща скоба в израз.

Намерете индекс на затваряща скоба за дадена отваряща скоба в израз

Пример

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

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

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

index = 0
-1

Подход

Употреба купчина структура на данните на цяло число type, за да съхраните индекса на отварящите скоби в дадения низ. Започнете да преглеждате даденото низ като се започне от дадения индекс. Ако се срещне отваряща скоба, натиснете я в стека. За всяка срещаща се затваряща скоба, извадете отваряща скоба от стека. Ако стекът се изпразни, т.е. размерът на стека е 0 при някакъв индекс, отпечатайте индекса. Друг печат -1.

алгоритъм

  1. Инициализирайте низ s дължина / размер n и цяло число, представляващо индекса на отваряща квадратна скоба.
  2. Създайте функцията, за да намерите индекс на затварящата скоба за дадената отваряща скоба в дадения низ, която приема стойност на низ, представляваща израз и целочислена стойност, представляваща индекса на отваряща скоба в дадения низ като параметър.
  3. Проверете дали символът при даден индекс не е равен на отваряща скоба, т.е. '[', print -1 и return.
  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), защото използвахме пространство за съхраняване на символите на дадения низ. Сложността на пространството зависи от броя на скобите. Но в най-лошия случай всички знаци може да са в квадратни скоби. Така космическата сложност също е линейна.

Препратки