પેરેંટિસિસ લેટકોડ સોલ્યુશનની મહત્તમ માળખાની thંડાઈ


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે બ્લૂમબર્ગ
શબ્દમાળા

સમસ્યા નિવેદન

આ સમસ્યામાં, અમને માન્ય કૌંસ આપવામાં આવે છે શબ્દમાળા (vps) માં કેટલાક નંબરો, કેટલાક .પરેટર્સ (દા.ત. +, -, *) અને કેટલાક કૌંસ (દા.ત. '(', ')') હોય છે.
માન્ય કૌંસ શબ્દમાળાઓ (vps) છે:

  1.  ""
  2. "ડી" જ્યાં ડી કોઈપણ સંખ્યા છે
  3. “(એ)” જો એ માન્ય કૌંસ શબ્દમાળા છે
  4. “એ * બી” જો * કોઈ ઓપરેટર છે અને એ અને બી માન્ય કૌંસ શબ્દમાળા છે.

આપણો હેતુ આપેલ શબ્દમાળામાં કૌંસની મહત્તમ depthંડાઈ શોધવાનો છે.
e.g. “(1+(2*3)+((8)/4))+1”
આપણે જોઈ શકીએ છીએ કે નંબર 8 એ કૌંસની મહત્તમ સંખ્યાની અંદર છે અને કૌંપની depthંડાઈ 3 છે. આપણે 3 આઉટપુટ કરીશું.

પેરેંટિસિસ લેટકોડ સોલ્યુશનની મહત્તમ માળખાની thંડાઈ
ચાલો એક વધુ ઉદાહરણ જોઈએ,
e.g. “1+(2*3)/(2-1)”
vps 2 * 3 અથવા બીજા vps 2-1, બંને કૌંસની મહત્તમ depthંડાઈ એટલે કે 1 ની અંદર હોય છે.

ઉદાહરણ

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

સમજૂતી:

અંક 8 એ શબ્દમાળામાં 3 નેસ્ટેડ કૌંસની અંદર છે.

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

અભિગમ

અમને આપવામાં આવ્યું છે કે શબ્દમાળા એક vps છે અને આપણે ફક્ત કૌંસની મહત્તમ depthંડાઈ શોધવા પડશે. તેથી, અમે ફક્ત કૌંસ પર ધ્યાન કેન્દ્રિત કરી શકીએ છીએ અને અન્ય અક્ષરો (નંબર અને operaપરેટર્સ) ને અવગણી શકીએ છીએ.

કૌંસની Theંડાઈ ફક્ત ત્યારે જ વધે છે જ્યારે ત્યાં નવી નેસ્ટડ કૌંસ શરૂ થાય છે. એટલે કે પ્રારંભિક કૌંસ '(' નો અર્થ એ કે કૌંસની depthંડાઈમાં 1 નો વધારો થાય છે. અને જ્યારે કૌંસ બંધ થાય છે, ત્યારે depthંડાઈ 1. દ્વારા ઘટે છે. એટલે કે ')' એટલે કે depthંડાઈ 1 દ્વારા ઘટાડે છે.

અમારા અભિગમમાં આપણે ફક્ત વર્તમાન depthંડાઈ ચલ (ચાલો કે) અને મહત્તમ depthંડાઈ ચલ (જવાબો આપીશું) નો ઉપયોગ કરીશું .બંને 0 થી આરંભ કરવામાં આવે છે (depthંડાઈ 0 નો અર્થ છે કે આપણે શરૂઆતમાં બધી કૌંસમાંથી બહાર નીકળીએ છીએ). અને ઇનપુટ શબ્દમાળાને ડાબેથી જમણે જવાનું પ્રારંભ કરો. અમે જે યુક્તિની ચર્ચા કરી છે તે મુજબ, જ્યારે પણ આપણે કોઈ '(' નિશાનીનો સામનો કરીશું ત્યારે આપણે વર્તમાન depthંડાઈ k ને 1 દ્વારા વધારીશું અને જ્યારે પણ આપણે કોઈનો સામનો કરીશું ') ચિહ્ન આપણે વર્તમાન depthંડાઈ k ને 1 દ્વારા ઘટાડીશું.
દરેક વખતે અમે તપાસ કરીશું કે વર્તમાન depthંડાઈ મહત્તમ depthંડાઈ કરતા વધારે છે કે નહીં. જો હા તો આપણે મહત્તમ depthંડાઈ ચલને વર્તમાન depthંડાઈ સોંપીશું.
આખરે ટ્રversવર્સલ પછી, અમારા એન્સિસ વેરીએબલએ મહત્તમ depthંડાઈ સંગ્રહિત કરી છે, તેથી અમે તેને આઉટપુટ કરીશું

અમલીકરણ

પેરેંટિસિસ લેટકોડ સોલ્યુશનની મહત્તમ માળખાની thંડાઈ માટે સી ++ પ્રોગ્રામ

#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

પેરેંટિસિસ લેટકોડ સોલ્યુશનની મહત્તમ માળખાની forંડાઈ માટે જાવા પ્રોગ્રામ

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

પેરેંટિસિસ લેટકોડ સોલ્યુશનની મહત્તમ માળખાની thંડાઈ માટે જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન): અમે આપેલ અભિવ્યક્તિને ડાબેથી જમણે ખસેડી રહ્યા છીએ. આમ તે ઓ (એન) છે જ્યાં n આપેલ શબ્દમાળાની લંબાઈ છે.

અવકાશ જટિલતા 

ઓ (1): અમે સતત વધારાની જગ્યાઓનો ઉપયોગ કર્યો નથી. આમ જગ્યા જટિલતા ઓ (1) છે.