Problem:
Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.
Note: The input string may contain letters other than the parentheses ( and ).
Examples:
|
1 2 3 |
"()())()" -> ["()()()", "(())()"] "(a)())()" -> ["(a)()()", "(a())()"] ")(" -> [""] |
题目大意：给你一个字符串，由”(” “)”和其他字符构成。让你删除数量最少的括号使得表达式合法（括号都匹配）。输出所有的合法表达式。
Idea:
Search 
Solution: DFS
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
// Author: Huahua // Runtime: 0 ms class Solution { public: vector<string> removeInvalidParentheses(const string& s) { int l = 0; int r = 0; for (const char ch : s) { l += (ch == '('); if (l == 0) r += (ch == ')'); else l -= (ch == ')'); } vector<string> ans; dfs(s, 0, l, r, ans); return ans; } private: bool isValid(const string& s) { int count = 0; for (const char ch : s) { if (ch == '(') ++count; if (ch == ')') --count; if (count < 0) return false; } return count == 0; } // l/r: number of left/right parentheses to remove. void dfs(const string& s, int start, int l, int r, vector<string>& ans) { // Nothing to remove. if (l == 0 && r == 0) { if (isValid(s)) ans.push_back(s); return; } for (int i = start; i < s.length(); ++i) { // We only remove the first parenthes if there are consecutive ones to avoid duplications. if (i != start && s[i] == s[i - 1]) continue; if (s[i] == '(' || s[i] == ')') { string curr = s; curr.erase(i, 1); if (r > 0 && s[i] == ')') dfs(curr, i, l, r - 1, ans); else if (l > 0 && s[i] == '(') dfs(curr, i, l - 1, r, ans); } } } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment