ஒரு வெளிப்பாட்டில் கொடுக்கப்பட்ட திறப்பு அடைப்புக்குறி அடைப்பை அடைப்பதற்கான குறியீட்டைக் கண்டறியவும்


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அடோப் அமேசான் , Flipkart ஆரக்கிள் OYO அறைகள் Snapdeal வால்மார்ட் ஆய்வகங்கள் யாத்ரா
அணி ஸ்டேக் சரம்

சிக்கல் அறிக்கை

கொடுக்கப்பட்ட ஒரு சரம் கள் நீளம் / அளவு n மற்றும் தொடக்க சதுர அடைப்புக்குறியின் குறியீட்டைக் குறிக்கும் ஒரு முழு மதிப்பு. ஒரு வெளிப்பாட்டில் கொடுக்கப்பட்ட தொடக்க அடைப்புக்குறி அடைப்பு அடைப்பின் குறியீட்டைக் கண்டறியவும்.

ஒரு வெளிப்பாட்டில் கொடுக்கப்பட்ட திறப்பு அடைப்புக்குறி அடைப்பை அடைப்பதற்கான குறியீட்டைக் கண்டறியவும்

உதாரணமாக

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.

குறியீடு

அடைப்புக்குறியைத் திறப்பதற்கான தொடர்புடைய அடைப்பு அடைப்பைக் கண்டறிய சி ++ நிரல்

#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

அடைப்புக்குறியைத் திறப்பதற்கான தொடர்புடைய மூடு அடைப்பைக் கண்டுபிடிக்க ஜாவா நிரல்

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 என்பது கொடுக்கப்பட்ட சரத்தின் நீளம். சரத்தில் கிடைக்கும் எல்லா எழுத்துக்களுக்கும் மேலாக நாம் பயணித்திருப்பதால், நேர சிக்கலானது நேரியல்.

விண்வெளி சிக்கலானது

O (n) ஏனெனில் கொடுக்கப்பட்ட சரத்தின் எழுத்துக்களை சேமிக்க நாங்கள் இடத்தைப் பயன்படுத்தினோம். இட சிக்கலானது அடைப்புக்குறிகளின் எண்ணிக்கையைப் பொறுத்தது. ஆனால் மோசமான நிலையில், எல்லா எழுத்துக்களும் சதுர அடைப்புக்குறிகளாக இருக்கலாம். இதனால் விண்வெளி சிக்கலானது நேரியல் ஆகும்.

குறிப்புகள்