在表达式中查找给定开口支架的闭合支架索引  


难度级别 易得奖学金
经常问 土砖 亚马逊 Flipkart 神谕 OYO房间 Snapdeal 沃尔玛实验室 朝圣
排列

问题陈述  

给定一个 绳子 s的长度/大小为n,并且它是一个表示方括号的索引的整数。 在表达式中查找给定左括号的右括号索引。

在表达式中查找给定开口支架的闭合支架索引Pin

使用案列  

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),因为我们使用空间来存储给定字符串的字符。 空间复杂度取决于括号的数量。 但在最坏的情况下,所有字符都可能是方括号。 因此,空间复杂度也是线性的。

參考資料