leetcode 301. 删除无效的括号
删除最小数量的无效括号，使得输入的字符串有效，返回所有可能的结果。
说明: 输入可能包含了除 ( 和 ) 以外的字符。
示例 1:
输入: “()())()”
输出: [“()()()”, “(())()”]
示例 2:
输入: “(a)())()”
输出: [“(a)()()”, “(a())()”]
示例 3:
输入: “)(”
输出: [“”]
说明: 输入可能包含了除 ( 和 ) 以外的字符。
示例 1:
输入: “()())()”
输出: [“()()()”, “(())()”]
示例 2:
输入: “(a)())()”
输出: [“(a)()()”, “(a())()”]
示例 3:
输入: “)(”
输出: [“”]
思路：用checkleft 和checkright从左到右和从右到左分别检查并删除可能多出来的"("和")",将所有可能的字符串分别压入Q，而且是无重复（need哈希表），再对Q中的每一个进行上述步骤。
vector<string>res;
queue<String> Q;
set<string>visit;
vector<String> removeInvalid(String s);
void check(String s, vector<String>res);
bool checkLeft(String s, vector<String> res);
bool checkRight(String s, vector<String> res);
vector<String> removeInvalid(String s)
{ Q.push(s); visit.insert(s); bool flag = false; while (!Q.empty()) { String cur = Q.front(); Q.pop(); if (flag) { check(cur,res); } else { flag = checkLeft(cur,res) || checkRight(cur,res); } } if (res.size() == 0) { res.push_back(""); } return res;
}
void check(String s,vector<String>res)
{ stack<char> stack1; for (int i = 0; i < s.size();++i) { if (s[i]=='(') { stack1.push(s[i]); } if (s[i]==')') { if (stack1.empty()) return; } stack1.pop(); } if (stack1.empty()) { res.push_back(s); }
}
bool checkLeft(String s,vector<String> res)
{ stack<char> s1; for (int i = 0; i < s.size(); ++i) { if (s[i] == '(') { s1.push(s[i]); } else if (s[i]==')') { if (s1.empty()) { for (int j = i; j >= 0;--j) { if (s[j] == ')') { String str = s.substr(0, j) + s.substr(j + 1); if (visit.find(str)==visit.end()) { Q.push(str); visit.insert(str); } } } return false; } else { s1.pop(); } } } if (s1.empty()) { res.push_back(s); return true; } return false;
}
bool checkRight(String s,vector<string>res)
{ stack<char>s1; for (int i = s.size() - 1; i >= 0; --i) { if (s[i]==')') { s1.push(s[i]); } else if (s[i] == '(') { if (s1.empty()) { for (int j = i; j < s.size(); ++j) { if (s[j] == '(') { String str = s.substr(0, j) + s.substr(j+1); if (visit.find(str) == visit.end()) { Q.push(str); visit.insert(str); } } } return false; } else { s1.pop(); } } } if (s1.empty()) { res.push_back(s); return true; } return false;
}
查看7道真题和解析