Commite4783c4

committed

remove_invalid_parentheses

1 parent6eb479c commite4783c4Copy full SHA for e4783c4

File tree

+43

-0

lines changed

+43

-0

lines changed

Lines changed: 1 addition & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -216,6 +216,7 @@ Golang solution for leetcode. For each problem, there is a simple *_test.go to t`
`216`	`216`	`####[297. Serialize and Deserialize Binary Tree](https://github.com/hitzzc/go-leetcode/tree/master/serialize_and_deserialize_binary_tree)`
`217`	`217`	`####[299. Bulls and Cows](https://github.com/hitzzc/go-leetcode/tree/master/bulls_and_cows)`
`218`	`218`	`####[300. Longest Increasing Subsequence](https://github.com/hitzzc/go-leetcode/tree/master/longest_increasing_subsequence)`
	`219`	`+####[301. Remove Invalid Parentheses](https://github.com/hitzzc/go-leetcode/tree/master/remove_invalid_parentheses)`
`219`	`220`
`220`	`221`
`221`	`222`

Lines changed: 42 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,42 @@`
	`1`	`+#include<string>`
	`2`	`+#include<unordered_set>`
	`3`	`+usingnamespacestd;`
	`4`	`+`
	`5`	`+classSolution {`
	`6`	`+public:`
	`7`	`+ vector<string>removeInvalidParentheses(string s) {`
	`8`	`+int left =0;`
	`9`	`+int right =0;`
	`10`	`+for (auto ch: s) {`
	`11`	`+if (ch =='(') ++left;`
	`12`	`+if (ch ==')') {`
	`13`	`+if (left >0) --left;`
	`14`	`+else ++right;`
	`15`	`+ }`
	`16`	`+ }`
	`17`	`+ vector<string> results;`
	`18`	`+ unordered_set<string> unique;`
	`19`	`+DFS(s,0,0, left, right,"", results, unique);`
	`20`	`+return results;`
	`21`	`+ }`
	`22`	`+`
	`23`	`+voidDFS(string&s,int idx,int pair,int left,int right, string solution, vector<string>& results, unordered_set<string>& unique) {`
	`24`	`+if (idx == s.size()) {`
	`25`	`+if (left ==0 && right ==0 && pair ==0 && unique.find(solution) == unique.end()) {`
	`26`	`+ results.push_back(solution);`
	`27`	`+ unique.insert(solution);`
	`28`	`+ }`
	`29`	`+return;`
	`30`	`+ }`
	`31`	`+if (s[idx] =='(') {`
	`32`	`+if (left >0)DFS(s, idx+1, pair, left-1, right, solution, results, unique);`
	`33`	`+DFS(s, idx+1, pair+1, left, right, solution+"(", results, unique);`
	`34`	`+ }elseif (s[idx] ==')') {`
	`35`	`+if (right >0)DFS(s, idx+1, pair, left, right-1, solution, results, unique);`
	`36`	`+if (pair >0)DFS(s, idx+1, pair-1, left, right, solution+")", results, unique);`
	`37`	`+ }else {`
	`38`	`+DFS(s, idx+1, pair, left, right, solution+s[idx], results, unique);`
	`39`	`+ }`
	`40`	`+return;`
	`41`	`+ }`
	`42`	`+};`

Comments

(0)