LeetCode: Generate Parenthesis

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