Максимална дубина гнежђења решења у облику заграде у облику заграде


Ниво тешкоће Лако
Често питани у Блоомберг
низ

Изјава о проблему

У овом проблему добијамо важеће заграде низ (впс) који имају неке бројеве, неке операторе (нпр. +, -, *) и неке заграде (нпр. '(', ')').
Важећи низови заграда (впс) су:

  1.  ""
  2. „Д“ где је д било који број
  3. „(А)“ ако је А важећи низ заграда
  4. „А * Б“ ако је * било који оператор, а А и Б су важећи низ заграда.

Циљ нам је да пронађемо максималну дубину заграда у датом низу.
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

objašnjenje:

Знаменка 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).