Найти индекс закрывающей скобки для данной открывающей скобки в выражении


Сложный уровень Легко
Часто спрашивают в саман Амазонка Flipkart Oracle OYO Номера Snapdeal Walmart Labs ятра
массив Стек строка

Постановка задачи

Учитывая строка 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. Инициализировать строку длины / размера 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), потому что мы использовали пробел для хранения символов данной строки. Сложность пространства зависит от количества скобок. Но в худшем случае все символы могут быть в квадратных скобках. Таким образом, сложность пространства также линейна.

дело