پیرینٹیز لیٹکوڈ حل کی گھوںسلا کی زیادہ سے زیادہ گہرائی


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے بلومبرگ
سلک

مسئلہ یہ بیان

اس پریشانی میں ، ہمیں ایک درست قوسین دیا گیا ہے سٹرنگ (vps) میں کچھ نمبر ، کچھ آپریٹرز (جیسے + ، - ، *) اور کچھ قوسین (جیسے '(' ، ')') ہیں۔
درست قوسین تار (vps) یہ ہیں:

  1.  ""
  2. "d" جہاں d کوئی بھی تعداد ہے
  3. "(A)" اگر A درست قوسین تار ہے
  4. "A * B" اگر * کوئی آپریٹر ہے اور A اور B درست قوسین تار ہیں۔

ہمارا مقصد یہ ہے کہ دی گئی تار میں قوسین کی زیادہ سے زیادہ گہرائی کو تلاش کرنا ہے۔
e.g. “(1+(2*3)+((8)/4))+1”
ہم دیکھ سکتے ہیں کہ نمبر 8 میں قوسین کی زیادہ سے زیادہ تعداد کے اندر ہے اور قوسین کی گہرائی 3 ہے۔ ہم پیداوار 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 کا مطلب ہے کہ ہم شروع میں تمام قوسین سے دور ہیں)۔ اور ان پٹ تار کو بائیں سے دائیں جانا شروع کریں۔ اس چال کے مطابق جس پر ہم نے تبادلہ خیال کیا ، جب بھی ہم کسی '(' نشانی کا سامنا کریں گے ہم موجودہ گہرائی 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): ہم دیئے گئے اظہار کو بائیں سے دائیں منتقل کررہے ہیں۔ اس طرح یہ O (n) ہے جہاں n دیئے گئے تار کی لمبائی ہے۔

خلائی پیچیدگی 

O (1): ہم نے مستقل اضافی جگہیں استعمال نہیں کیں۔ اس طرح خلائی پیچیدگی O (1) ہے۔