NC255. 最长有效的括号字符子序列
描述
示例1
输入:
"()())"
输出:
["(())","()()"]
说明:
2个都是最长的，长度都为4，["()()","(())"]也是一个正确的答案示例2
输入:
")("
输出:
[""]
示例3
输入:
"(a))"
输出:
["(a)"]
说明:
只有一个有效且最长的C++ 解法, 执行用时: 3ms, 内存消耗: 548KB, 提交时间: 2022-05-29
class Solution {
public:
int maxscore;
int length;
int n;
unordered_set<string> hash;
//左括号是1分 右括号 是-1分 合规的字符串一定时是0
void dfs(string s, int score,string buf,int l,int r,int index){
//如果出现删过头或者分数出现负数或者超过最大数返回
if(l<0||r<0||score<0||score>maxscore)
return;
if(l==0&&r==0&&buf.length()==length)
hash.insert(buf);
if(index==n)
return;
char ch = s[index];
if(ch=='('){
dfs(s, score + 1, buf + '(', l, r, index + 1);//选择添加（括号 则+1分 继续遍历
dfs(s, score, buf, l - 1, r, index + 1);//选择不添加左括号相当于删除左括号 则分数不变 继续遍历
}
else if(ch==')'){
dfs(s, score - 1, buf + ')', l, r, index + 1);//选择添加）括号 则-1分 继续遍历
dfs(s, score, buf, l, r - 1, index+1);//选择不添加右括号相当于删除右括号 则分数不变 继续遍历
}else{
dfs(s, score, buf + ch, l, r, index + 1);//遇到其他字符 直接添加 继续遍历
}
}
vector<string> maxValidParenthesesStr(string s){
//合规的字符串 分数一定是0
//分数一定不会超过maxscore，maxscore就是所有可匹配的(都在左边，一直+1，能达到的最大分数
maxscore = 0;
n = s.size();
int left = 0;
int right = 0;
int l = 0, r = 0;
length = 0;
for(auto&ch:s){
if(ch=='('){
//统计左括号的数量
//需要删除的左括号的数量
l++;
left++;
}
else if(ch==')'){
//统计右括号数量
if(l!=0)
l--;//遇到可能匹配的右括号
else
r++;//需要删除的右括号的数量
right++;
}
}
length = n - l - r;//字符串中除了左括号和右括号以外的应该有的长度
maxscore = left < right ? left : right;//最大分数为可匹配的左括号或右括号的数量
dfs(s, 0, "", l, r, 0);
return {hash.begin(), hash.end()};
}
};
C++ 解法, 执行用时: 4ms, 内存消耗: 480KB, 提交时间: 2022-05-09
class Solution {
public:
bool isValid(string str) {
int count = 0;
for (char c : str) {
if (c == '(') {
count++;
} else if (c == ')') {
count--;
if (count < 0) {
return false;
}
}
}
return count == 0;
}
vector<string> maxValidParenthesesStr(string s) {
vector<string> ans;
unordered_set<string> currSet;
currSet.insert(s);
while (true) {
for (auto & str : currSet) {
if (isValid(str))
ans.emplace_back(str);
}
if (ans.size() > 0) {
return ans;
}
unordered_set<string> nextSet;
for (auto & str : currSet) {
for (int i = 0; i < str.size(); i++) {
if (i > 0 && str[i] == str[i - 1]) {
continue;
}
if (str[i] == '(' || str[i] == ')') {
nextSet.insert(str.substr(0, i) + str.substr(i + 1, str.size()));
}
}
}
currSet = nextSet;
}
}
};
C++ 解法, 执行用时: 5ms, 内存消耗: 500KB, 提交时间: 2022-07-15
class Solution {
public:
int maxscore;
int length;
int n;
unordered_set<string> hash;
//左括号是1分 右括号 是-1分 合规的字符串一定时是0
void dfs(string s, int score,string buf,int l,int r,int index){
//如果出现删过头或者分数出现负数或者超过最大数返回
if(l<0||r<0||score<0||score>maxscore)
return;
if(l==0&&r==0&&buf.length()==length)
hash.insert(buf);
if(index==n)
return;
char ch = s[index];
if(ch=='('){
dfs(s, score + 1, buf + '(', l, r, index + 1);//选择添加（括号 则+1分 继续遍历
dfs(s, score, buf, l - 1, r, index + 1);//选择不添加左括号相当于删除左括号 则分数不变 继续遍历
}
else if(ch==')'){
dfs(s, score - 1, buf + ')', l, r, index + 1);//选择添加）括号 则-1分 继续遍历
dfs(s, score, buf, l, r - 1, index+1);//选择不添加右括号相当于删除右括号 则分数不变 继续遍历
}else{
dfs(s, score, buf + ch, l, r, index + 1);//遇到其他字符 直接添加 继续遍历
}
}
vector<string> maxValidParenthesesStr(string s){
//合规的字符串 分数一定是0
//分数一定不会超过maxscore，maxscore就是所有可匹配的(都在左边，一直+1，能达到的最大分数
maxscore = 0;
n = s.size();
int left = 0;
int right = 0;
int l = 0, r = 0;
length = 0;
for(auto&ch:s){
if(ch=='('){
//统计左括号的数量
//需要删除的左括号的数量
l++;
left++;
}
else if(ch==')'){
//统计右括号数量
if(l!=0)
l--;//遇到可能匹配的右括号
else
r++;//需要删除的右括号的数量
right++;
}
}
length = n - l - r;//字符串中除了左括号和右括号以外的应该有的长度
maxscore = left < right ? left : right;//最大分数为可匹配的左括号或右括号的数量
dfs(s, 0, "", l, r, 0);
return {hash.begin(), hash.end()};
}
};
Java 解法, 执行用时: 16ms, 内存消耗: 9992KB, 提交时间: 2022-03-05
import java.util.*;
public class Solution {
private List<String> res = new ArrayList<String>();
private List<String> ans= new ArrayList<String>();
public String[] maxValidParenthesesStr(String s) {
int lremove = 0;
int rremove = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
lremove++;
} else if (s.charAt(i) == ')') {
if (lremove == 0) {
rremove++;
} else {
lremove--;
}
}
}
helper(s, 0, lremove, rremove);
String[] strings = new String[res.size()];
return res.toArray(strings);
}
private void helper(String str, int start, int lremove, int rremove) {
if (lremove == 0 && rremove == 0) {
if (isValid(str)) {
res.add(str);
}
return;
}
for (int i = start; i < str.length(); i++) {
if (i != start && str.charAt(i) == str.charAt(i - 1)) {
continue;
}
// 如果剩余的字符无法满足去掉的数量要求，直接返回
if (lremove + rremove > str.length() - i) {
return;
}
// 尝试去掉一个左括号
if (lremove > 0 && str.charAt(i) == '(') {
helper(str.substring(0, i) + str.substring(i + 1), i, lremove - 1, rremove);
}
// 尝试去掉一个右括号
if (rremove > 0 && str.charAt(i) == ')') {
helper(str.substring(0, i) + str.substring(i + 1), i, lremove, rremove - 1);
}
}
}
private boolean isValid(String str) {
int cnt = 0;
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == '(') {
cnt++;
} else if (str.charAt(i) == ')') {
cnt--;
if (cnt < 0) {
return false;
}
}
}
return cnt == 0;
}
}
Java 解法, 执行用时: 17ms, 内存消耗: 9864KB, 提交时间: 2022-03-12
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @return string字符串一维数组
*/
List<String> res = new ArrayList<>();
public String[] maxValidParenthesesStr (String s) {
int lRemove = 0;
int rRemove = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
lRemove++;
}
else if (s.charAt(i) == ')') {
if (lRemove == 0) rRemove++;
else lRemove--;
}
}
helper(s, 0, lRemove, rRemove);
String [] strings = new String[res.size()];
return res.toArray(strings);
}
void helper(String str, int start, int lRemove, int rRemove) {
if (lRemove == 0 && rRemove == 0) {
if (isValid(str)) {
res.add(str);
}
return;
}
for (int i = start; i < str.length(); i++) {
if (i != start && str.charAt(i) == str.charAt(i-1)) {
continue;
}
if (lRemove + rRemove > str.length() - i) {
return;
}
if (lRemove > 0 && str.charAt(i) == '(') {
helper(str.substring(0, i) + str.substring(i + 1), i, lRemove - 1, rRemove);
}
if (rRemove > 0 && str.charAt(i) == ')') {
helper(str.substring(0, i) + str.substring(i + 1), i, lRemove, rRemove - 1);
}
}
}
boolean isValid(String str) {
int cnt = 0;
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == '(') {
cnt++;
}
else if (str.charAt(i) == ')') {
cnt--;
if (cnt < 0) {
return false;
}
}
}
return cnt == 0;
}
}