题解 | #合法的括号字符串#
合法的括号字符串
https://www.nowcoder.com/practice/eceb50e041ec40bd93240b8b3b62d221
思路一：
顺着看，看右括号，每个右括号都有左括号或者*与之匹配
逆着看，看左括号，每个左括号都有右括号或者*与之匹配
bool isValidString(char* s ) {
// 每一个右括号都有一个左括号或者*与之匹配
int L=0,S=0,i=0;
while(s[i] != '\0'){
if(s[i] == '('){
L++;
}
else if(s[i] == '*'){
S++;
}
else if(s[i] == ')'){
if(L>0) L--;
else if(S>0) S--;
else return 0;
}
i++;
}
// 每一个左括号都有一个右括号或者*与之匹配
int R=0,S2=0;
i=strlen(s)-1;//注意是逆序，倒着看
while(s[i] != '\0'){
if(s[i] == ')'){
R++;
}
else if(s[i] == '*'){
S2++;
}
else if(s[i] == '('){
if(R>0) R--;
else if(S2>0) S2--;
else return 0;
}
i--;
}
if(L<=S && R<=S2) return 1;
else return 0;
}
思路二：
用链表，方便删除节点，没有实现
投递美团等公司9个岗位
查看30道真题和解析