coding problems and their solutions .
| name | tags |
|---|---|
| generate parenthesis | leetcode |
sliding window
subset pattern
modified binary search pattern
Top K elements pattern
binary tree Dfs
topologcal sort
binary tree Bfs
two pointer pattern
mostly works when data is sorted
| from time import time | |
| from typing import List, Set, Tuple | |
| class Solution: | |
| """ | |
| Tests: | |
| >>> result = Solution().generateParenthesis(3); all([c in result for c in ['((()))','(()())','(())()','()(())','()()()']]) | |
| True | |
| >>> result = Solution().generateParenthesis(1); all([c in result for c in ['()']]) | |
| True | |
| """ | |
| def generateParenthesis(self, n: int) -> List[str]: | |
| start = "()"*n | |
| result: Set[str] = set() | |
| result.add(start) | |
| self.run(start, result, memory=set()) | |
| return list(result) | |
| def run(self, pattern: str, track: Set[str], memory: Set[tuple] = None): | |
| combinations = self.make_combinations(pattern, memory=memory) | |
| if combinations : | |
| for combination in combinations: | |
| if isinstance(memory, set) and (..., combination) not in memory: | |
| track.add(combination) | |
| memory.add((..., combination)) | |
| self.run(combination, track, memory=memory) | |
| else: | |
| track.add(combination) | |
| self.run(combination, track, memory=memory) | |
| def make_combinations(self, value:str, memory: Set[tuple]): | |
| """ | |
| >>> make_combinations("()()(())", memory=None) | |
| ['((()))()', '()((()))'] | |
| >>> make_combinations("((()))", memory=None) | |
| [] | |
| >>> make_combinations("(()())", memory=None) | |
| [] | |
| """ | |
| to_insert, insert_in = self.insert(value=value) | |
| combinations: list = [] | |
| if isinstance(memory, set): | |
| if (to_insert, insert_in) in memory: | |
| return combinations | |
| else: | |
| memory.add((to_insert, insert_in)) | |
| i = 0 | |
| while i < len(insert_in): | |
| if insert_in[i] == "(": | |
| comb: str = insert_in[:i+1] + to_insert + insert_in[i+1:] | |
| combinations.append(comb) | |
| i += 1 | |
| return combinations | |
| def insert(self, value:str): | |
| """ | |
| >>> insert("()()()()") | |
| ('()', '()()()') | |
| >>> insert("()()(())") | |
| ('(())', '()()') | |
| """ | |
| to_insert = "" | |
| i = len(value) - 1 | |
| open = 0 | |
| while True: | |
| char = value[i] | |
| to_insert = char + to_insert | |
| if char == "(": | |
| open -= 1 | |
| elif char == ")": | |
| open += 1 | |
| if open == 0: | |
| break | |
| i-=1 | |
| insert_in = value[:i] | |
| return to_insert, insert_in | |
| class Solution2: | |
| """ | |
| Tests: | |
| >>> result = Solution2().generateParenthesis(3); all([c in result for c in ['((()))','(()())','(())()','()(())','()()()']]) | |
| True | |
| >>> result = Solution2().generateParenthesis(1); all([c in result for c in ['()']]) | |
| True | |
| """ | |
| def run(self, pattern: str, n:int, stats: Tuple[int], store: List[str]): | |
| if stats[0] == 0: | |
| store.append(pattern + ")"*stats[1]) | |
| return | |
| if stats[1] < 0: | |
| return | |
| # if stats[1] == 0: | |
| # self.run(pattern + "(", n, (stats[0]-1, stats[1]+1), store) | |
| # else: | |
| self.run(pattern + "(", n, (stats[0]-1, stats[1]+1), store) | |
| self.run(pattern + ")", n, (stats[0], stats[1]-1), store) | |
| def generateParenthesis(self, n: int) -> List[str]: | |
| res: List[str] = [] | |
| self.run("", n, (n, 0), store=res) | |
| return res | |
| class Solution3: | |
| """ | |
| Tests: | |
| >>> result = Solution2().generateParenthesis(3); all([c in result for c in ['((()))','(()())','(())()','()(())','()()()']]) | |
| True | |
| >>> result = Solution2().generateParenthesis(1); all([c in result for c in ['()']]) | |
| True | |
| """ | |
| def run(self, pattern: str, n:int, remaining_brackets: int, open_brackets: int): | |
| if remaining_brackets == 0: | |
| return [pattern + ")"*open_brackets] | |
| if open_brackets < 0: | |
| return [] | |
| return self.run(pattern + "(", n, remaining_brackets-1, open_brackets+1,) + self.run(pattern + ")", n, remaining_brackets, open_brackets-1,) | |
| def generateParenthesis(self, n: int) -> List[str]: | |
| return self.run("", n, n, 0) | |
| if __name__ == '__main__': | |
| t1 = time() | |
| print(Solution3().generateParenthesis(8)) | |
| print(time()-t1) | |
| """ | |
| My Rough Work : | |
| ()()() | |
| ()(()) (())() | |
| ((())) (()()) | |
| () ()() | |
| (())() | |
| ()(()) | |
| ----------------- x ----------------- x ----------------- | |
| n=3 | |
| x=1 | |
| ( left, to_close) | |
| when left == 0, backtrack | |
| 2,1 | |
| (( () | |
| 1,2 2,0 | |
| (() ((( ()( | |
| 1,1 0,3 <--B 1,1 | |
| (()) (()( ()() ()(( | |
| 1,0 0,2 <--B 1,0 0,2 <--B | |
| (())( ()()( | |
| 0,1 <--B 0,1 <--B | |
| ----------------- x ----------------- x ----------------- | |
| 1, 4, 2 | |
| "()" + "()" + "()" + "()" | |
| a b c d | |
| ()()()() | |
| (())()() ()(())() ()()(()) | |
| (()())() ((()))() (())(()) | |
| """ |