कोष्ठक लेटेकोड समाधान के अधिकतम घोंसले के शिकार गहराई


कठिनाई स्तर आसान
में अक्सर पूछा ब्लूमबर्ग
तार

समस्या का विवरण

इस समस्या में, हमें एक वैध कोष्ठक दिया जाता है स्ट्रिंग (vps) कुछ संख्याएँ, कुछ ऑपरेटर (जैसे +, - *) और कुछ कोष्ठक (जैसे '(', '))।
मान्य कोष्ठक तार (vps) हैं:

  1.  ""
  2. “D” जहाँ d कोई संख्या है
  3. "(ए)" यदि ए वैध कोष्ठक स्ट्रिंग है
  4. "ए * बी" यदि * कोई ऑपरेटर है और ए और बी वैध कोष्ठक स्ट्रिंग हैं।

हमारा उद्देश्य दिए गए स्ट्रिंग में कोष्ठकों की अधिकतम गहराई का पता लगाना है।
e.g. “(1+(2*3)+((8)/4))+1”
हम देख सकते हैं कि 8 नंबर पर कोष्ठक की अधिकतम संख्या के अंदर है और वहाँ कोष्ठक की गहराई 3. 3 है। हम XNUMX आउटपुट करेंगे।

कोष्ठक लेटेकोड समाधान के अधिकतम घोंसले के शिकार गहराई
आइए एक और उदाहरण देखें,
e.g. “1+(2*3)/(2-1)”
vps 2 * 3 या दूसरा vps 2-1, दोनों कोष्ठक की अधिकतम गहराई अर्थात 1 के अंदर हैं।

उदाहरण

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

स्पष्टीकरण:

अंक 8 स्ट्रिंग में 3 नेस्टेड कोष्ठकों के अंदर है।

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

दृष्टिकोण

हमें दिया गया है कि स्ट्रिंग एक vps है और हमें केवल कोष्ठक की अधिकतम गहराई का पता लगाना है। इसलिए, हम केवल कोष्ठकों पर ध्यान केंद्रित कर सकते हैं और अन्य पात्रों (संख्याओं और ऑपरेटरों) को अनदेखा कर सकते हैं।

कोष्ठकों की गहराई तभी बढ़ती है जब एक नया नेस्टेड कोष्ठक शुरू होता है। यानी शुरुआती कोष्ठक '(' का अर्थ है कि कोष्ठक की गहराई में 1. की वृद्धि होती है और जब कोष्ठक बंद हो जाता है, तो गहराई 1. से कम हो जाती है। '' 'का अर्थ है कि गहराई 1 से कम हो गई है।

हमारे दृष्टिकोण में हम बस एक वर्तमान गहराई चर (k) और अधिकतम गहराई चर (ans दें) का उपयोग करेंगे। दोनों को 0 से आरंभ किया जाता है (गहराई 0 का मतलब है कि हम शुरू में सभी कोष्ठकों से बाहर हैं)। और इनपुट स्ट्रिंग को बाईं से दाईं ओर ट्रेस करना शुरू करें। हमने जिस ट्रिक पर चर्चा की है, उसके अनुसार जब भी हम एक '(' साइन करेंगे) हम वर्तमान गहराई को 1 से बढ़ाएंगे और जब भी हमारा सामना होगा ') तो हम वर्तमान गहराई k को 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

कोष्ठक Leetcode समाधान के अधिकतम घोंसले के शिकार के लिए जावा कार्यक्रम

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

कोष्ठक Leetcode समाधान की अधिकतम घोंसले के शिकार के लिए जटिलता विश्लेषण

समय जटिलता

पर): हम दी गई अभिव्यक्ति को बाएं से दाएं की ओर ले जा रहे हैं। इस प्रकार यह O (n) है जहां n दी गई स्ट्रिंग की लंबाई है।

अंतरिक्ष जटिलता 

ओ (1): हमने निरंतर अतिरिक्त स्थान का उपयोग नहीं किया है। इस प्रकार अंतरिक्ष जटिलता O (1) है।