Илэрхийлэлд өгөгдсөн нээлтийн хаалтанд хаагдах хаалтны индексийг олох  


Хэцүү байдлын түвшин Easy
Байнга асуудаг Adobe Амазоны Flipkart Oracle-ийн OYO өрөөнүүд Snapdeal Walmart лабораторууд Ятра
Array Stack String

Асуудлын мэдэгдэл  

Өгсөн мөр урт / хэмжээтэй s ба нээлтийн дөрвөлжин хаалтны индексийг илэрхийлэх бүхэл тоо. Өгүүлэлд өгөгдсөн нээлтийн хаалтанд хаалтын хаалтны индексийг ол.

Илэрхийлэлд өгөгдсөн нээлтийн хаалтанд хаагдах хаалтны индексийг олохPin

Жишээ нь  

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

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

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

index = 0
-1

арга барил  

А стек өгөгдлийн бүтэц бүхэл тоо өгөгдсөн мөрөнд нээх хаалтны индексийг хадгалахын тулд бичнэ үү. Өгөгдсөн зүйлээр дамжуулан давтаж эхлээрэй мөр өгөгдсөн индексээс эхэлнэ. Хэрэв нээлтийн хаалт тулгарвал түүнийг стек рүү түлхэх хэрэгтэй. Хаалттай хаалт бүрт стекээс нээх хаалтыг гаргаж ирнэ. Хэрэв стек хоосон бол өөрөөр хэлбэл стекийн хэмжээ зарим индекс дээр 0 байвал индексийг хэвлэ. Бусад хэвлэх -1.

Алгоритм  

  1. Урт / хэмжээтэй мөрийг эхлүүлэх n ба нээлтийн дөрвөлжин хаалтны индексийг илэрхийлсэн бүхэл тоон утга.
  2. Өгөгдсөн мөрөнд илэрхийлэлийг илэрхийлсэн мөрийн утга ба өгөгдсөн мөрөнд нээгдэх хаалтны индексийг илэрхийлэх бүхэл тоон утгыг хүлээн авсан өгөгдсөн мөрөнд өгөгдсөн нээлтийн хаалтанд хаах хаалтны индексийг олох функцийг үүсгээрэй.
  3. Өгөгдсөн индекс дээрх тэмдэгт нь нээх хаалттай тэнцэхгүй байгаа эсэхийг шалгана уу, өөрөөр хэлбэл '[', хэвлээд -1, буцаана.
  4. Үүний дараа өгөгдсөн мөрийн нээлтийн хаалтын индексийг хадгалахын тулд бүхэл тоон төрлийн стек өгөгдлийн бүтцийг бий болгоно.
  5. Өгөгдсөн индексээс өгөгдсөн мөрийг дайран өнгөрөөд мөр доторх тухайн үеийн индексийн тэмдэгт нээх хаалттай тэнцүү байгаа эсэхийг шалгаад тухайн индекс дээрх тэмдэгтийг стек дэх мөрөнд оруул / оруулна уу.
  6. Хэрэв мөр дэх одоогийн индекс дээрх тэмдэгт хаалтын хаалттай тэнцүү байвал өөрөөр хэлбэл ']' байвал стекийн дээд хэсэгт байрлах элементийг арилгана. Үүний дараа стек хоосон байгаа эсэхийг шалгана уу, өөрөөр хэлбэл стекийн хэмжээ 0-тэй тэнцүү байна, одоо байгаа индексийг хэвлээд буцаана.
  7. Хэвлэх -1.
мөн үзнэ үү
Backspace мөрийг харьцуулах

код  

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), учир нь бид өгөгдсөн мөрийн тэмдэгтүүдийг хадгалах зай ашигласан. Сансрын нарийн төвөгтэй байдал нь хаалтны тооноос хамаарна. Гэхдээ хамгийн муу тохиолдолд бүх тэмдэгтүүд дөрвөлжин хаалт байж болно. Тиймээс орон зайн нарийн төвөгтэй байдал нь мөн шугаман юм.

Ашигласан материал