पॅरेंथेसिस लीटकोड सोल्यूशनची अधिकतम घरटी खोली


अडचण पातळी सोपे
वारंवार विचारले ब्लूमबर्ग
अक्षरमाळा

समस्या विधान

या समस्येमध्ये आम्हाला वैध कंस दिले गेले आहे स्ट्रिंग (vps) मध्ये काही क्रमांक, काही ऑपरेटर (उदा. +, -, *) आणि काही कंस (उदा. '(', ')') आहेत.
वैध कंस तार (vps) आहेत:

  1.  ""
  2. “D” जेथे d ही संख्या आहे
  3. “(ए)” जर अ वैध कंसांची स्ट्रिंग असेल तर
  4. “ए * बी” जर * कोणताही ऑपरेटर असेल तर आणि ए आणि बी वैध कंस आहेत.

आमचे उद्दीष्ट दिलेल्या स्ट्रिंगमध्ये कंसांची कमाल खोली शोधणे आहे.
e.g. “(1+(2*3)+((8)/4))+1”
आपण पाहु शकतो की व्या क्रमांकावर कंसात कमाल संख्या आहे आणि कंसांची खोली आहे 8. आपण आउटपुट 3 करू.

पॅरेंथेसिस लीटकोड सोल्यूशनची अधिकतम घरटी खोली
चला अजून एक उदाहरण पाहू.
e.g. “1+(2*3)/(2-1)”
व्हीपीएस 2 * 3 किंवा दुसर्या व्हीपीएस 2-1, दोन्ही कंसांच्या कमाल खोलीच्या आत म्हणजे 1.

उदाहरण

s = "(1+(2*3)+((8)/4))+1"
3

स्पष्टीकरण:

अंक 8 स्ट्रिंगमधील 3 नेस्टेड कंसात आहेत.

s = "(1)+((2))+(((3)))"
3

दृष्टीकोन

आम्हाला दिले गेले आहे की स्ट्रिंग एक व्हीपीएस आहे आणि आपल्याला कंसात जास्तीत जास्त खोली शोधणे आवश्यक आहे. तर, आम्ही फक्त कंस वर लक्ष केंद्रित करू आणि इतर वर्ण (संख्या आणि ऑपरेटर) कडे दुर्लक्ष करू.

जेव्हा नवीन नेस्टेड कंस सुरू होते तेव्हाच कंसात खोली वाढते. म्हणजे प्रारंभ कंस '(' याचा अर्थ कोष्ठकांची खोली 1 ने वाढते. आणि जेव्हा कंस बंद होते तेव्हा खोली 1 ने कमी होते. म्हणजे ')' म्हणजे खोली 1 ने कमी होते.

आमच्या दृष्टीकोनात आपण फक्त सखोल डीप व्हेरिएबल (चला के) आणि जास्तीत जास्त डीप व्हेरिएबल (उत्तर द्या) वापरू .तर 0 ने आरंभ केला आहे (खोली 0 म्हणजे आम्ही सुरुवातीच्या काळात सर्व कंसात आहोत). आणि इनपुट स्ट्रिंग डावीकडून उजवीकडे वळविणे प्रारंभ करा. आम्ही ज्या युक्तीवर चर्चा केली त्यानुसार, जेव्हा जेव्हा आपल्याला '(' चिन्ह मिळेल तेव्हा आम्ही सध्याची खोली के 1 ने वाढवू आणि जेव्हा जेव्हा आपल्याला 'चे' चे चिन्ह मिळेल) तेव्हा आम्ही सध्याची खोली के 1 ने कमी करू.
प्रत्येक वेळी आम्ही जास्तीत जास्त खोलीपेक्षा सद्य खोली जास्त आहे की नाही हे तपासू. जर होय असेल तर आम्ही जास्तीत जास्त खोलीतील चल करीता सखोल खोली लागू करू.
शेवटी ट्रॅव्हर्सल नंतर, आमच्या अन्स व्हेरिएबलने जास्तीत जास्त खोली साठवली आहे, म्हणून आपण हे आउटपुट करू.

अंमलबजावणी

पॅरेंथेसिस लीटकोड सोल्यूशनच्या जास्तीत जास्त घरट्यासाठी खोली + साठी सी ++ प्रोग्राम

#include <iostream>
using namespace std;

int maxDepth(string s) 
{
    int ans=0,k=0;
    for(int i=0;i<s.length();i++)
    {
        if(s[i]=='(')k++;
        else if(s[i]==')')k--;
        ans=ans>k?ans:k;
    }
    return ans;
}
int main()
{
    cout<<maxDepth("(1)+((2))+(((3)))");
}
3

पॅरेंथेसिस लीटकोड सोल्यूशनच्या जास्तीत जास्त घरट्यासाठी जावा प्रोग्राम

import java.util.*;
import java.lang.*;

class Solution
{  
    public static int maxDepth(String s) 
    {
        int ans=0,k=0;
        for(int i=0;i<s.length();i++)
        {
            if(s.charAt(i)=='(')k++;
            else if(s.charAt(i)==')')k--;
            ans=Math.max(ans,k);
        }
        return ans;
    }
    
    public static void main(String args[])
    {
        System.out.println(maxDepth("(1)+((2))+(((3)))"));
    }
}
3

पॅरेंथेसिस लीटकोड सोल्यूशनच्या जास्तीत जास्त घरटींच्या खोलीसाठी जटिलता विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन): आम्ही दिलेली अभिव्यक्ती डावीकडून उजवीकडे वळवित आहोत. अशा प्रकारे हे ओ (एन) आहे जेथे एन दिलेली स्ट्रिंगची लांबी आहे.

स्पेस कॉम्प्लेक्सिटी 

ओ (1): आम्ही सतत अतिरिक्त मोकळी जागा वापरली नाही. अशा प्रकारे अवकाश जटिलता ओ (1) आहे.