LeetCode: Generate Parenthesis

KangDroid·2021년 6월 27일

Algorithm

목록 보기

24/27

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;
    }
};