Generer parenteser Leetcode-løsning

Sværhedsniveau Medium
Ofte stillet ind Adobe Amazon æble Bloomberg ByteDance C3 IoT Facebook google Intuit microsoft Oracle Spotify Tesla Uber
backtracking Dynamisk programmering String Walmart Global teknologiViews 55

Systemdesign interviewspørgsmål kan være så åben, at det er for svært at kende den rigtige måde at forberede sig på. Nu er jeg i stand til at knække designrunderne fra Amazon, Microsoft og Adobe efter køb denne bog. Daglig revision af en design spørgsmål og jeg lover, at du kan knække designrunden.

Problemformulering

Generer parenteser LeetCode Solution – "Frembringe parenteser” angiver, at givet værdien af ​​n. Vi skal generere alle kombinationer af n par parenteser.

Returner svaret i form af en vektor af strenge af velformede parenteser.

Eksempel:

Input:  n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Forklaring:

  • Alle velformede parenteser er:- ["((()))",,"(()())","(())()",,"()(())",,"()() ()”].
Input:  n = 1
Output: ["()"]

Forklaring:

  • Alle velformede parenteser er:- [“()”].

Tilgang

Ide:

  1. Hovedideen til at løse dette problem er at bruge rekursion.
  2. Brute force-tilgangen er at overveje hver type parentes ved hvert indeks og gå til næste trin af rekursion og kontrollere, om dette fører til gyldige velformede parenteser? Hvis ja, gem strengen som vores svar, ellers gå tilbage.
  3. For en effektiv løsning, Start med en tom streng og n antal åbne og lukkede parenteser (da vi skal danne n par).
  4. At hvert trin af rekursion, gælder følgende tilfælde:
    1. Base sag: Når et antal åbne og lukkede parenteser er begge lig med n, gemmer den aktuelle streng som vores svar.
    2. Når antallet af åbne parenteser er strengt taget mindre end n, kan vi placere den åbne beslag nu.
    3. Når antallet af afsluttende parenteser er strengt taget mindre end antallet af lukkebeslag, skal vi placere lukkebeslaget nu.
  5. Hver gang vi når basiscaset, vil vi gemme strengen dannet i vores svar, som er de velformede parenteser.
  6. Returner alle de velformede parenteser som vores svar i form af en vektor af strenge.

Kode

Generer parenteser Leetcode C++ Løsning:

class Solution {
public:
    vector<string> ans;
    void recurse(string s,int open,int close,int n){
        if(open==n and close==n){
            ans.push_back(s);
            return;
        }
        if(open<n)
            recurse(s+"(",open+1,close,n);
        if(close<open)
            recurse(s+")",open,close+1,n);
    }
    vector<string> generateParenthesis(int n) {
        recurse("",0,0,n);
        return ans;
    }
};

Generer parenteser Leetcode Java-løsning:

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<String>();
        backtrack(list, "", 0, 0, n);
        return list;
    }
    public void backtrack(List<String> list, String str, int open, int close, int max){
        if(str.length() == max*2){
            list.add(str);
            return;
        }        
        if(open < max){
            backtrack(list, str+"(", open+1, close, max);
        }
        if(close < open){
            backtrack(list, str+")", open, close+1, max);
        }
    }
}

Kompleksitetsanalyse for Generer parenteser Leetcode-løsning

Tidskompleksitet

Tidskompleksiteten af ​​ovenstående kode er O(2^(2N)) da vi i værste fald skal overveje enhver mulighed for at åbne og lukke parenteser, hvor N = antallet af par, vi skal danne.

Rumkompleksitet

Rumkompleksiteten af ​​ovenstående kode er PÅ). 

Crack System Design Interviews
Translate »