Added BF Solution for Generate Paranthesis

anxious-coder-lhs · anxious-coder-lhs · commit c37b1e109d7c · 2020-10-13T09:00:16.000+05:30
diff --git a/README.md b/README.md
@@ -51,6 +51,7 @@ Happy to accept any contributions to this in any langugage.
 16. [LeetCode Web Crawler 1242](https://leetcode.com/problems/web-crawler-multithreaded/) | [Solution 1 ](./level_medium/LeetCode_WebCrawler_MultiThreaded_1242.java) | [Solution 2](level_medium/LeetCode_WebCrawler_MultiThreaded_1242_1.java)
 17. [Leet Code 554 Brick Wall](https://leetcode.com/problems/brick-wall/) | [Solution 1](./level_medium/LeetCode_554_Brick_Wall_Medium.ts)
 18. [Leet Code 1190 Reverse Substrings Between Each Pair of Paranthesis](https://leetcode.com/problems/reverse-substrings-between-each-pair-of-parentheses/) | [Solution 1](level_medium/LeetCode_1190_Reverse_Substrings.ts) | [Solution Optimized](level_medium/LeetCode_1190_Reverse_Substrings_1.ts)
+19. [Leet Code 22 Generate Paranthesis](https://leetcode.com/problems/generate-parentheses/) | [Solution Brute Force](level_medium/LeetCode_22_Generate_Paranthesis_1.ts)
 
 
 ## Hard
diff --git a/level_medium/LeetCode_22_Generate_Paranthesis_1.ts b/level_medium/LeetCode_22_Generate_Paranthesis_1.ts
@@ -0,0 +1,56 @@
+/**
+ * Problem: Leet Code 22
+ * Solution: Uses a brute force approach of creating all the possible permutations.
+ * Basic fundamental of permutation is making all the possible choices at each step.
+ * As we explore all the possible choices at each step, the solution space will explode
+ * for us leading to an exponential solution. We use recursion to explore and a base condition
+ * to stop where all the positions for the choices have been explored.
+ * 
+ * Complexity: Time O(2^n * n) since the entire permutation space has to be explored.
+ * Additionally, each string also needs to be validated for correctness in O(n) time.
+ * Space: O(2^n) assuming all the possible strings are valid.
+ * 
+ * @param n 
+ */
+function generateParenthesis(n: number): string[] {
+    return generateParanthesisHelper(n * 2)
+};
+
+function generateParanthesisHelper(n: number, curr: number = 0, result: string[] = []): string[] {
+        
+    const output: string[] = [];
+    
+    if (curr >= n) {
+        // Done for all the positions, validate the created string.
+        if (isValidParanthesis(result))
+            output.push(result.join(""))
+
+        return output;
+    }
+    
+    // At the position curr, choose one of the braces and recursively move.
+    result[curr] = "("
+    output.push(...generateParanthesisHelper(n, curr + 1, result));
+    
+    // At the position curr, choose one of the braces and recursively move.
+    result[curr] = ")"
+    output.push(...generateParanthesisHelper(n, curr + 1, result));
+    
+    // Return the final results.
+    return output;
+
+}
+
+function isValidParanthesis(result: string[]) {
+    let braces = 0;
+    for (let idx = 0; idx < result.length; idx++) {
+        if (result[idx] === "(") braces++
+        else if (result[idx] === ")") braces--;
+        
+        if (braces < 0) return false
+    }
+    
+    return braces === 0;
+}
+
+console.log(generateParenthesis(3))
