301. Remove Invalid Parentheses
invalid remove 301 Parentheses
2023-09-11 14:22:45 时间
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 )
.
Example 1:
Input: "()())()" Output: ["()()()", "(())()"]
Example 2:
Input: "(a)())()" Output: ["(a)()()", "(a())()"]
Example 3:
Input: ")(" Output: [""]
Approach #1: C++.
class Solution { public: vector<string> removeInvalidParentheses(string s) { int l = 0; int r = 0;
// calculate the mismatch parentheses. for (char c : s) { l += (c == '('); if (l == 0) { r += (c == ')'); } else { l -= (c == ')'); } } vector<string> ans; dfs(s, 0, l, r, ans); return ans; } private: bool isValid(string& s) { int count = 0; for (char c : s) { if (c == '(') count++; if (c == ')') count--; if (count < 0) return false; } return count == 0; } void dfs(string s, int start, int l, int r, vector<string>& ans) { if (l == 0 && r == 0) { if (isValid(s)) // judge the string is valid. ans.push_back(s); return; } for (int i = start; i < s.length(); ++i) { if (i != start && s[i] == s[i-1]) continue;
// s[i] is '(' or ')' if (s[i] == '(' || s[i] == ')') { string curr = s; curr.erase(i, 1); if (r > 0) dfs(curr, i, l, r-1, ans); else if (l > 0) dfs(curr, i, l-1, r, ans); } } } };
Analysis:
step1: compute min number of '(' and ')' to remove, unbalanced ')' + unblanced '('
step2: try all possible ways to remove r '(' and l ')'. Remove '(' first to make prefix valid.
step3: when r == 0 and l == 0, judging the string is or not fulfiled conditions.
相关文章
- Leetcode: Remove Invalid Parentheses
- kentico中提示Message: An invalid SQL query was used.
- UnicodeDecodeError: ‘utf-8‘ codec can‘t decode byte 0xd3 in position 5: invalid continuation byte
- Google Earth Engine——Error: Image.clipToBoundsAndScale, argument ‘input‘: Invalid type的错误解决
- MySQL Invalid default value for datetime
- kafka消费者报错INVALID_FETCH_SESSION_EPOCH
- C++释放指针时提示Invalid address specified to RtlFreeHeap解决办法(堆栈中分配时多分配一些空间再释放)
- 【AGC】publishing api contentRating in cds serviceAttr is invalid问题分析
- mybatis 异常处理:Invalid bound statement (not found)
- IOS APP报错:SyntaxError: Invalid regular expression: invalid group specifier name __ERROR
- python pdf加水印,出错UnicodeDecodeError: ‘utf-8‘ codec can‘t decode byte 0xcb in position 8: invalid cont
- 解决python manage.py时报错:File "manage.py", line 17 from excs ^ SyntaxError: invalid syntax
- find 命令解决mv: invalid option -- ‘E‘和Argument list too long问题
- [LeetCode] 301. Remove Invalid Parentheses 移除非法括号
- Spring initializr Error:java: 读取C:Users….m2repositorycomfasterxmljacksoncorejackson-databind2.9.8jackson-databind-2.9.8.jar时出错; ZipFile invalid LOC header (bad signature)
- nginx: [error] invalid PID number "" in "/usr/local/webserver/nginx/logs/nginx.pid" (原)
- groovy-2.4.11.jar时出错; invalid LOC header (bad signature)
- Chrome 安装离线插件时报 CRX_HEADER_INVALID