在表達式中查找給定開口支架的閉合支架索引


難度級別 容易獎學金
經常問 土磚 亞馬遜 Flipkart 神諭 OYO房間 Snapdeal 沃爾瑪實驗室 朝聖
排列

問題陳述

給定一個 s的長度/大小為n,並且它是一個表示方括號的索引的整數。 在表達式中查找給定左括號的右括號索引。

在表達式中查找給定開口支架的閉合支架索引

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

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

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

index = 0
-1

途徑

使用 的數據結構 整數 鍵入以在給定的字符串中存儲左括號的索引。 開始遍歷給定 從給定的索引開始。 如果遇到開口支架,請將其推入堆棧。 對於遇到的每個閉合括號,從堆棧中彈出一個開口括號。 如果堆棧變空,即在某個索引處堆棧的大小為0,請打印索引。 其他打印-1。

算法

  1. 初始化長度/大小的字符串s 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),因為我們使用空間來存儲給定字符串的字符。 空間複雜度取決於括號的數量。 但在最壞的情況下,所有字符可能都是方括號。 因此,空間複雜度也是線性的。

參考