కుండలీకరణాలు లీట్‌కోడ్ పరిష్కారం యొక్క గరిష్ట గూడు లోతు


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది బ్లూమ్బెర్గ్
స్ట్రింగ్

సమస్యల నివేదిక

ఈ సమస్యలో, మాకు చెల్లుబాటు అయ్యే కుండలీకరణాలు ఇవ్వబడతాయి స్ట్రింగ్ (vps) కొన్ని సంఖ్యలు, కొన్ని ఆపరేటర్లు (ఉదా. +, -, *) మరియు కొన్ని కుండలీకరణాలు (ఉదా. '(', ')').
చెల్లుబాటు అయ్యే కుండలీకరణాల తీగలు (vps):

  1.  ""
  2. “D” ఇక్కడ d అనేది ఏదైనా సంఖ్య
  3. “చెల్లుబాటు అయ్యే కుండలీకరణ స్ట్రింగ్ అయితే“ (ఎ) ”
  4. “A * B” ఉంటే * ఏదైనా ఆపరేటర్ మరియు A మరియు B చెల్లుబాటు అయ్యే కుండలీకరణ స్ట్రింగ్.

ఇచ్చిన స్ట్రింగ్‌లో కుండలీకరణాల గరిష్ట లోతును కనుగొనడం మా లక్ష్యం.
e.g. “(1+(2*3)+((8)/4))+1”
8 సంఖ్య వద్ద గరిష్ట సంఖ్యలో కుండలీకరణాలు మరియు కుండలీకరణాల లోతు 3 ఉన్నట్లు మనం చూడవచ్చు. మేము అవుట్పుట్ 3 చేస్తాము.

కుండలీకరణాలు లీట్‌కోడ్ పరిష్కారం యొక్క గరిష్ట గూడు లోతు
మరో ఉదాహరణ చూద్దాం,
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 తగ్గుతుంది.

మా విధానంలో మనం ప్రస్తుత లోతు వేరియబుల్ (లెట్ కె) మరియు గరిష్ట లోతు వేరియబుల్ (లెట్ అన్స్) ను ఉపయోగిస్తాము .అది 0 కి ప్రారంభించబడింది (లోతు 0 అంటే మనం మొదట్లో అన్ని కుండలీకరణాల్లో లేము). మరియు ఇన్పుట్ స్ట్రింగ్ను ఎడమ నుండి కుడికి ప్రయాణించడం ప్రారంభించండి. మేము చర్చించిన ట్రిక్ ప్రకారం, మనం ఒక '(' గుర్తును ఎదుర్కొన్నప్పుడల్లా మేము ప్రస్తుత లోతు k ని 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

కుండలీకరణాలు లీట్‌కోడ్ సొల్యూషన్ యొక్క గరిష్ట గూడు లోతు కోసం జావా ప్రోగ్రామ్

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

కుండలీకరణాల లీట్‌కోడ్ పరిష్కారం యొక్క గరిష్ట గూడు లోతు కోసం సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

పై): మేము ఇచ్చిన వ్యక్తీకరణను ఎడమ నుండి కుడికి ప్రయాణిస్తున్నాము. అందువలన ఇది O (n), ఇక్కడ n ఇచ్చిన స్ట్రింగ్ యొక్క పొడవు.

అంతరిక్ష సంక్లిష్టత 

ఓ (1): మేము స్థిరమైన అదనపు ఖాళీలను ఉపయోగించలేదు. అందువల్ల స్థల సంక్లిష్టత O (1).