LeetCode: Generate Parenthesis

8289 ワード

テキストリンク

Question

https://leetcode.com/problems/generate-parentheses

Level: Medium

Type: DFS

Core Logic

Intuitive[First Attempt]

So, first, I thought just searching all-possible-parentheses and checking whether those generated parenthesis is valid or not would be great though

It passed[accepted], but it took 136ms and that is 5% of people who made this.[So top 95%]

Search All possible one -> Check whether is valid -> Valid? push to answer.

Optimized Logic

So, after my solution was accepted, I looked up solution[more likely, discussion] for more optimization and was also curious whether how other people made it more faster[like 4ms or less].

Most of people used DFS Search algorithm like me, but there was a huge difference.

Checking whether generated parenthesis are valid was the one.

Basically the way I check whether generated parenthesis takes about O(size)

So roughly, total O(N^2) or more I bet

But looking at the pattern of valid parenthesis that, they always have equal number of single parenthesis.

So, checking with each open-close parenthesis count[whether same or not] would be the first attempt to reduce search space.

Now, we are 'making' the parenthesis, not 'checking' it.

Each open/close parenthesis could be added ONLY n times

So we are not allowing the case like ((((((((

If, open count of parenthesis is smaller then close parenthesis, we can close parenthesis to make valid parenthesis

So the core logic of this optimized logic would be

Instead of checking generated parenthesis, just make valid parenthesis

Code

class Solution {
public:
    vector<string> correctAnswer;
    
    void dfs(string& generatedString, int currentDepth, int& pairCount, int openCount, int endCount) {
        if (currentDepth == pairCount*2) {
            if (openCount != 0 || openCount != 0) return;
            correctAnswer.push_back(generatedString);
            return;
        }
        
        if (openCount > 0) {
            generatedString.push_back('(');
            dfs(generatedString, currentDepth+1, pairCount, openCount-1, endCount);
            generatedString.pop_back();
        }
        
        if (openCount < endCount) {
            generatedString.push_back(')');
            dfs(generatedString, currentDepth+1, pairCount, openCount, endCount-1);
            generatedString.pop_back();
        } 
    }
    vector<string> generateParenthesis(int n) {
        string tmpValue = "";
        dfs(tmpValue, 0, n, n, n);
        
        return correctAnswer;
    }
};

Submission

The log of attempts..

136ms to 4ms lol

Reference

この問題について(LeetCode: Generate Parenthesis), 我々は、より多くの情報をここで見つけました https://velog.io/@kangdroid/LeetCode-Generate-Parenthesis

テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。

Collection and Share based on the CC Protocol

[プログラマー]牛乳とヨーグルトがいっぱい入ったショッピングバスケット(MySQL)

RMAN delete noprompt obsoleteパラメータ研究