Берилген ачылыш кронштейн үчүн жабык кронштейндин индексин табыңыз  


Кыйынчылык деңгээли жеңил
Көп суралган Adobe Amazon Flipkart Oracle OYO бөлмөлөр Snapdeal Walmart Labs Yatra
согуштук тизме чөмөлө аркан

Маселени билдирүү  

Берилген а аркан узундугу / көлөмү н жана ачылуучу төрт бурчтуу кашаанын индексин көрсөткөн бүтүн сан. Берилген ачылыш кашаа үчүн жабуунун кашаа индексин табыңыз.

Берилген ачылыш кронштейн үчүн жабык кронштейндин индексин табыңыз

мисал  

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

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

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

index = 0
-1

жакындоо  

Колдонуу чөмөлө маалыматтардын структурасы бүтүн берилген сапта ачылуучу кашаанын индексин сактоо үчүн териңиз. Берилген аркылуу кайталоону баштаңыз аркан берилген индекстен баштап. Эгерде ачылуучу кашаа кездешсе, аны үймөктө түртүп салыңыз. Кезиккен ар бир жабуучу кашаа үчүн, стектен ачылуучу кашаанын ачылышы. Эгерде стек бош болуп калса, башкача айтканда, стектин көлөмү кандайдыр бир индексте 0 болсо, индексти басып чыгарыңыз. Else print -1.

Algorithm  

  1. Узундугу / көлөмү болгон s сапты баштаңыз n жана ачылуучу квадрат кашаанын индексин чагылдырган бүтүн сан.
  2. Берилген тилкеде берилген ачылуучу кашаа үчүн жабылуучу кашаанын индексин табуу функциясын түзүңүз, ал өрнекти билдирген сап маанисин жана берилген саптагы ачылуучу кашаанын индексин көрсөткөн бүтүн санды, анткени бул параметр.
  3. Берилген индекстеги белгинин ачылуучу кашаага барабар эместигин текшериңиз, башкача айтканда '[', басып чыгаруу -1 жана кайтаруу.
  4. Андан кийин, берилген саптын ачылуучу кашаанын индексин сактоо үчүн бүтүн типтеги стек маалыматтар структурасын түзүңүз.
  5. Берилген индекстен баштап берилген сапты аралап өтүп, саптагы учурдагы индекстеги символ ачылуучу кашаага барабар экендигин текшериңиз, стекдеги саптагы учурдагы индекстеги белгини түртүп киргизиңиз.
  6. Эгерде саптагы учурдагы индекстеги символ жабылуучу кронштейнге барабар болсо, башкача айтканда '' ', стектин жогору жагындагы элементти чыгарып / алып салыңыз. Андан кийин, стек бош экендигин текшерип, башкача айтканда, стектин көлөмү 0го барабар болуп, учурдагы индексти басып чыгарып, кайтып келиңиз.
  7. Басып чыгаруу -1.
ошондой эле
Backspace String салыштыруу

коду  

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), анткени биз берилген саптын белгилерин сактоо үчүн орун колдондук. Космостун татаалдыгы кашаанын санына жараша болот. Бирок эң начар учурда, бардык белгилер төрт бурчтуу кашаа болушу мүмкүн. Ошентип космостогу татаалдык да сызыктуу.

шилтемелер