给定一个字符串s，字符串s只包含以下三种字符: (，*，)，请你判断 s是不是一个合法的括号字符串。合法括号字符串有如下规则:
1.左括号'('必须有对应的右括号')'
2.右括号')'必须有对应的左括号'('
3.左括号必须在对应的右括号前面
4.*可以视为单个左括号，也可以视为单个右括号，或者视为一个空字符
5.空字符串也视为合法的括号字符串
数据范围:
[编程题]合法的括号字符串
需要正序和倒序遍历两遍，分别把星号当做左括号和右括号。从左往右遍历，把星号视为左括号，在遍历的过程中如果出现左括号数量比右括号数量少就返回false；然后从右往左遍历，把星号视为右括号，在遍历的过程中如果出现右括号数量比左括号少就返回false。两趟遍历下来还没返回false就返回true。
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @return bool布尔型
*/
public boolean isValidString (String s) {
// write code here
int left = 0, right = 0, star = 0;
for(int i = 0; i < s.length(); i++){
char c = s.charAt(i);
if(c == '('){
left ++;
}else if(c == ')'){
right ++;
}else{
star ++;
}
if(left + star < right) return false;
}
left = 0;
right = 0;
star = 0;
for(int i = s.length() - 1; i >= 0; i--){
char c = s.charAt(i);
if(c == '('){
left ++;
}else if(c == ')'){
right ++;
}else{
star ++;
}
if(right + star < left) return false;
}
return true;
}
}
发表于 2021-12-26 22:25:18
回复(1)
贪心算法逻辑：
1. 使用一个 low 表示最少剩余未匹配的 '('
2. 使用一个 high 表示最多剩余未匹配的 '('
3. 当出现 '(' 时，上述都要加一，表示未匹配数
4. 当出现 ')' 时, 表示可以匹配一个 '(' , low 和 high 都要减少
5. 当出现 '*' 时，则考虑极端情况，如果 * 代表 ) 则 low -1， 如果 * 代表 ( 则 high +1
6. 当出现 low < 0 时，说明有太多的 * 被视为 ')' , 需要将 low 置为0， 表示有部分的 '*' 被置为了空串而不是 ')' , 这是中间的状态
7. 而当 high <0 时，则说明遇到了太多的 ')'， 即使所有的 '*' 都置为了 '(’ (使得high++), 匹配完全部的 '(' 也会有剩余的 ')'
8. 全部结束时，如果 low == 0 说明全部的 ( 都可以匹配完，此时应该为 true
总结：这种做法理解起来较为困难，需要多动动脑子
具体代码如下：
public boolean isValidString (String s) {
int low = 0;
int high = 0;
for (char c : s.toCharArray()) {
if (c == '(') {
// 对于 '('，两个计数器都增加
low++;
high++;
} else if (c == ')') {
// 对于 ')'，两个计数器都减少
low--;
high--;
} else if (c == '*') {
// 对于 '*'，low 可以减少，high 可以增加
low--;
high++;
}
// low 不应该小于 0
if (low < 0) {
low = 0;
}
// 如果 high 变为负数，意味着太多的右括号无法匹配
if (high < 0) {
return false;
}
}
// 如果 low 为 0，则说明存在一种可能的 '*' 分配方式使得所有括号都匹配
return low == 0;
}
发表于 2024-05-08 16:04:00
回复(0)
可能出现错误的情况只有1、")n个((((..." 2、"(n个((((..)"，n>=0; 因此当出现这两种情况时返回false即可
public boolean isValidString (String s) {
int m=0,n=0;
for(int i=0;i<s.length();i++){
if(s.charAt(i)==')')m--;
else m++;
if(s.charAt(s.length()-1-i)=='(')n--;
else n++;
if(m<0||n<0)return false;
}
return true;
}
发表于 2022-05-14 22:23:11
回复(2)
import java.util.*;
/**
* NC175 合法的括号字符串
* @author d3y1
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @return bool布尔型
*/
public boolean isValidString (String s) {
return solution1(s);
// return solution2(s);
// return solution3(s);
}
/**
* 栈
* @param s
* @return
*/
private boolean solution1(String s){
Stack<Integer> leftStack = new Stack<>();
Stack<Integer> starStack = new Stack<>();
char ch;
for(int i=0; i<s.length(); i++){
ch = s.charAt(i);
if(ch == '('){
leftStack.push(i);
}
else if(ch == '*'){
starStack.push(i);
}
else if(ch == ')'){
if(!leftStack.isEmpty()){
leftStack.pop();
}else if(!starStack.isEmpty()){
starStack.pop();
}else{
return false;
}
}
}
while(!leftStack.isEmpty()){
if(!starStack.isEmpty() && leftStack.peek()<starStack.peek()){
leftStack.pop();
starStack.pop();
}else{
return false;
}
}
return true;
}
/**
* 贪心
* @param s
* @return
*/
private boolean solution2(String s){
// 待消除左括号的最小个数
int minLeft = 0;
// 待消除左括号的最大个数
int maxLeft = 0;
for(char ch: s.toCharArray()){
if(ch == '('){
minLeft++;
maxLeft++;
}
else if(ch == '*'){
// * -> )
if(minLeft > 0){
minLeft--;
}
// * -> (
maxLeft++;
}
else if(ch == ')'){
if(minLeft > 0){
minLeft--;
}
// 已经没有'('或'*'与当前')'匹配
if(maxLeft == 0){
return false;
}
maxLeft--;
}
}
return minLeft==0;
}
/**
* 动态规划
*
* dp[i][j]表示子串s[i,j]是否为合法的括号字符串
*
* len=1:
* dp[i][i] = true , s.charAt(i) == '*'
*
* len=2:
* dp[i][i+1] = true , (currCh=='('||currCh=='*') && (nextCh==')'||nextCh=='*')
*
* len>=3:
* dp[i][j] = dp[i+1][j-1] , (leftCh=='('||leftCh=='*') && (rightCh==')'||rightCh=='*')
* dp[i][j] = dp[i][k]&&dp[k+1][j] , i<=k<j&&!dp[i][j]
*
* @param s
* @return
*/
private boolean solution3(String s){
int n = s.length();
boolean[][] dp = new boolean[n][n];
// len=1 -> *
for(int i=0; i<n; i++){
if(s.charAt(i) == '*'){
dp[i][i] = true;
}
}
// len=2 -> () (* *) **
char currCh,nextCh;
for(int i=0; i+1<n; i++){
currCh = s.charAt(i);
nextCh = s.charAt(i+1);
if((currCh=='('||currCh=='*') && (nextCh==')'||nextCh=='*')){
dp[i][i+1] = true;
}
}
// len>=3
char leftCh,rightCh;
for(int i=n-3; i>=0; i--){
for(int j=i+2; j<n; j++){
leftCh = s.charAt(i);
rightCh = s.charAt(j);
// (())
if((leftCh=='('||leftCh=='*') && (rightCh==')'||rightCh=='*')){
dp[i][j] = dp[i+1][j-1];
}
// ()()
// for(int k=i; k<j&&!dp[i][j]; k++){
// dp[i][j] = dp[i][k]&&dp[k+1][j];
// }
for(int k=i; k<j; k++){
if(dp[i][j]){
break;
}
dp[i][j] = dp[i][k]&&dp[k+1][j];
}
}
}
return dp[0][n-1];
}
}
发表于 2025-01-30 14:00:52
回复(0)
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param s string字符串
# @return bool布尔型
#
class Solution:
def isValidString(self , s: str) -> bool:
# write code here
star_stack = []
symbol_stack = []
for i in range(len(s)):
if s[i:i+1] == '(':
symbol_stack.append([i,'('])
elif s[i:i+1] == '*':
star_stack.append([i,'*'])
else:
if symbol_stack:
symbol_stack.pop()
continue
elif len(symbol_stack) == 0 and star_stack:
star_stack.pop()
continue
else:
return False
while symbol_stack:
if len(star_stack) == 0:
return False
if symbol_stack.pop()[0] > star_stack.pop()[0]:
return False
return True
编辑于 2024-03-06 21:37:52
回复(0)
我按自己逻辑编写1个，下面有个大佬的正则有点不太懂（***为啥可以替换为***，但明显，那位大佬的正则替换代码更简洁。
function isValidString(s) {
var stack = [];
var sArr = s.split('');
// 处理右括号
for(var i = 0; i < sArr.length; i++) {
var item = sArr[i];
if(item === '(' || item === '*') {
stack.push(item);
}
// 遇到右括号时，从栈里面去找最近的左括号，若找不到，则找最近的*号， 若依然找不到，则字符串无效
if(item === ')') {
var _stack = [...stack].reverse();
// 若栈为空，则字符串无效
if(_stack.length === 0) {
stack.push(-1);
break;
}
// 寻找最近的左括号或左星号，都没有，则字符串无效
var index = _stack.indexOf('(') > -1 ? _stack.indexOf('(') : _stack.indexOf('*');
if(index === -1) {
break;
}
// 将最近的左括号或左星号替换为空
stack[stack.length - index -1] = '';
}
}
stack = stack.filter(item => item !== '');
// stack数组情况，可能存在多余的左括号（ 和 多余的星号，将（和*相互抵消
for(var j = stack.length - 1; j >= 0; j--) {
if(stack[j] === '(') {
// 检查元素右侧是否存在星号，若存在，则将
var starIndex = stack.indexOf('*',j);
if(starIndex > -1) {
stack[j] = '';
stack[starIndex] = '';
} else {
break;
}
}
}
return stack.join('').replaceAll('*','').length === 0;
}
发表于 2023-10-20 00:04:36
回复(0)
已通过，代码如下（含注释）：
#include <stack>
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @return bool布尔型
*/
bool isValidString(string s) {
// write code here
if (s.size() == 0) return true;
// 先清除可以匹配的()，如(*())(()))变成(*))
stack<char> chs;
for (char ch : s) {
if (ch == ')') {
if (chs.empty()) {
return false;
}
else if (chs.top() == '(') {
chs.pop();
}
else {
chs.push(ch);
}
}
else {
chs.push(ch);
}
}
// 如果末尾为(，必非法
if (!chs.empty() && chs.top() == '(') return false;
// 连接剩下的字符串
s = "";
while (!chs.empty()) {
s = chs.top() + s;
chs.pop();
}
return isMatch(s);
}
// 判断字符串是否能够匹配，即*适当转变之后能够匹配()
bool isMatch(string s) {
/**
* 判断是否存在)(的情况，存在则分开字符串分别再次匹配
* 如*)(((*)，看似3个(，2个)，可以将一个*转变为)，但是它非法
* 此时需将*)和(((*)分别判断，前者匹配后者否，所以非法
*/
int pos = -1;
for (int i = 1; i < s.size(); i++) {
if (s[i - 1] == ')' && s[i] == '(') {
pos = i;
break;
}
}
/**
* 不存在)(的情况，直接判断是否匹配，
* 只需(的数量与)的数量差值不大于*的数量，
* 则*可以适当转变(或)使得匹配
*/
if (pos < 0) {
int left = 0, right = 0, mid = 0;
for (char ch : s) {
if (ch == '(') {
left++;
}
else if (ch == ')') {
right++;
}
else if (ch == '*') {
mid++;
}
}
return abs(left - right) <= mid;
}
// 存在)(的情况，分开字符串分别再次匹配，即递归
string left = s.substr(0, pos);
string right = s.substr(pos, s.size() - pos);
return isMatch(left) && isMatch(right);
}
};
发表于 2023-07-15 00:56:31
回复(0)
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @return bool布尔型
*/
bool isValidString(char* s ) {
// write code here
int a = strlen(s);
int i, b = 0, c = 0, b1 = 0, c1 = 0;
for(i = 0;i< a;i++)
{
if(*(s + i) == '(') b++;
if(*(s + i) == ')') b--;
if(*(s + i) == '*') c++;
if((b + c) < 0) return false;
}
for(i = a-1;i>=0;i--)
{
if(*(s + i) == '(') b1--;
if(*(s + i) == ')') b1++;
if(*(s + i) == '*') c1++;
if((b1 + c1) < 0) return false;
}
if(b < 0) b= -b;
if(b == 0) return true;
if(b <= c) return true;
else return false;
}
发表于 2023-04-22 15:34:04
回复(0)
根据能成对的括号不断消除看最后是否只剩星号来判断是否是合法的括号字符串
function isValidString( s ) {
// write code here
// 根据星号数量和左右括号数量最少的数量的和和左右括号数量最多的数量作比较来淘汰不符合的字符
let leftCount = s.match(/\(/g)?s.match(/\(/g).length:0;
let rightCount = s.match(/\)/g)?s.match(/\)/g).length:0;
let xingCount = s.match(/\*/g)?s.match(/\*/g).length:0;
if(xingCount+Math.min(leftCount,rightCount) < Math.max(leftCount,rightCount)){
return false
}
else{
// 定义三个匹配模式匹配可以成对的括号
let pattern1 = /\((\**)\)/;//中间的括号用于捕获
let pattern2 = /\(\*/;//注意,这里不加g,是为了每次都能从头匹配
let pattern3 = /\*\)/;
while(pattern1.test(s)){
s = s.replace(/\((\**)\)/g,'$1');//$1是捕获的第一个数据
}
while(pattern2.test(s)){
s = s.replace(/\(\*/g,'');
}
while(pattern3.test(s)){
s = s.replace(/\*\)/g,'');
}
if(/^\**$/.test(s)){
return true
}else{
return false
}
}
}
发表于 2022-09-14 02:54:57
回复(1)
看看deepseek的脑回路吧！
class Solution:
def isValidString(self, s: str):
# 处理空字符串的情况
if not s:
return True
left_min, left_max = 0, 0
# 从左到右遍历，确保在任何位置右括号不会过多
for char in s:
if char == '(':
left_min += 1
left_max += 1
elif char == ')':
left_min = max(left_min - 1, 0)
left_max -= 1
else: # char == '*'
left_min = max(left_min - 1, 0)
left_max += 1
# 如果left_max小于0，说明右括号过多，无法匹配
if left_max < 0:
return False
# 最终左括号应该完全匹配
return left_min == 0
发表于 2025-10-24 14:43:41
回复(0)
class Solution:
def isValidString(self, s: str) -> bool:
low, high = 0, 0 # 维护左括号数量的最小、最大可能值
for c in s:
if c == '(':
low += 1
high += 1
elif c == ')':
if low > 0: # 尽量消耗左括号，减少最小可能
low -= 1
high -= 1 # 右括号必须匹配，最大可能减少
else: # c == '*'，三种情况取最优
if low > 0: # * 当右括号，减少最小可能
low -= 1
high += 1 # * 当左括号，增加最大可能
if high < 0: # 右括号过多，直接不合法
return False
return low <= 0
发表于 2025-07-13 20:00:32
回复(0)
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param s string字符串
# @return bool布尔型
#
class Solution:
def isValidString(self , s: str) -> bool:
# write code here
stack=[]
if(len(s)==0):
return True
count=0
for j in range(len(s)):
if(s[j]=='('):
count+=1
elif(s[j]==')'):
count-=1
if(count>=0):
for i in range(len(s)):
if(s[i]=='('):
stack.append(s[i])
if(s[i]==')'):
try:
stack.pop()
except:return False
if(s[i]=='*' and len(stack)!=0 and count!=0):
stack.pop()
count-=1
if(count<0):
for i in range(len(s)):
if(s[i]=='*'and count!=0):
stack.append(s[i])
count+=1
if(s[i]=='('):
stack.append(s[i])
if(s[i]==')'):
try:
stack.pop()
except:return False
if(len(stack)==0):
return True
else:return False 我在调试里面能输出正确值，但是在自测里又不行了，挺神奇
发表于 2025-07-09 17:38:47
回复(0)
需要用双栈，和压入下标的方法解答此题。
#include <string.h>
#include <stdbool.h>
#define MAXSIZE 100
#define NEEDNULL 0u
#define NEEDRIGHT 1u
#define NEDDLEFT 2U
typedef int ElementType;
typedef struct{
ElementType data[MAXSIZE];
int top;
}Stack;
void initStack(Stack *s)
{
s->top=-1;
}
bool isStackEmpty(Stack *s)
{
return s->top == -1;
}
bool isStackFull(Stack *s)
{
return s->top == (MAXSIZE-1);
}
bool Stackpush(Stack *s,ElementType item)
{
if(isStackFull(s))
return false;
s->data[++s->top]=item;
return true;
}
bool Stackpop(Stack *s,ElementType *item)
{
if(isStackEmpty(s))
return false;
*item = s->data[s->top--];
return true;
}
bool isValidString(char* s )
{
int i,leftnums=0,rightnums=0,dotnums=0,needchar=NEEDNULL;
Stack usrstack;
Stack starstack;
ElementType item,staritem;
initStack(&usrstack);
initStack(&starstack);
for(i=0;i<strlen(s);i++)
{
if(s[i]=='(')
leftnums++;
else if(s[i]==')')
rightnums++;
else if(s[i]=='*')
dotnums++;
}
if(leftnums>rightnums)
{
if(rightnums+dotnums<leftnums)
return false;
}
else if(rightnums>leftnums)
{
if(leftnums+dotnums<rightnums)
return false;
}
else {
}
for(i=0;i<strlen(s);i++)
{
if(s[i]=='(')
{
Stackpush(&usrstack,i);
}
else if(s[i]=='*' )
{
Stackpush(&starstack,i);
}
else if(s[i]==')')
{
if(!isStackEmpty(&usrstack))
Stackpop(&usrstack,&item);
else if(!isStackEmpty(&starstack))
Stackpop(&starstack,&item);
else
return false;
}
}
while(!isStackEmpty(&usrstack)&&!isStackEmpty(&starstack))
{
Stackpop(&usrstack, &item);
Stackpop(&starstack,&staritem);
if(item>staritem)
return false;
}
return isStackEmpty(&usrstack);
}
#include <stdbool.h>
#define MAXSIZE 100
#define NEEDNULL 0u
#define NEEDRIGHT 1u
#define NEDDLEFT 2U
typedef int ElementType;
typedef struct{
ElementType data[MAXSIZE];
int top;
}Stack;
void initStack(Stack *s)
{
s->top=-1;
}
bool isStackEmpty(Stack *s)
{
return s->top == -1;
}
bool isStackFull(Stack *s)
{
return s->top == (MAXSIZE-1);
}
bool Stackpush(Stack *s,ElementType item)
{
if(isStackFull(s))
return false;
s->data[++s->top]=item;
return true;
}
bool Stackpop(Stack *s,ElementType *item)
{
if(isStackEmpty(s))
return false;
*item = s->data[s->top--];
return true;
}
bool isValidString(char* s )
{
int i,leftnums=0,rightnums=0,dotnums=0,needchar=NEEDNULL;
Stack usrstack;
Stack starstack;
ElementType item,staritem;
initStack(&usrstack);
initStack(&starstack);
for(i=0;i<strlen(s);i++)
{
if(s[i]=='(')
leftnums++;
else if(s[i]==')')
rightnums++;
else if(s[i]=='*')
dotnums++;
}
if(leftnums>rightnums)
{
if(rightnums+dotnums<leftnums)
return false;
}
else if(rightnums>leftnums)
{
if(leftnums+dotnums<rightnums)
return false;
}
else {
}
for(i=0;i<strlen(s);i++)
{
if(s[i]=='(')
{
Stackpush(&usrstack,i);
}
else if(s[i]=='*' )
{
Stackpush(&starstack,i);
}
else if(s[i]==')')
{
if(!isStackEmpty(&usrstack))
Stackpop(&usrstack,&item);
else if(!isStackEmpty(&starstack))
Stackpop(&starstack,&item);
else
return false;
}
}
while(!isStackEmpty(&usrstack)&&!isStackEmpty(&starstack))
{
Stackpop(&usrstack, &item);
Stackpop(&starstack,&staritem);
if(item>staritem)
return false;
}
return isStackEmpty(&usrstack);
}
发表于 2025-01-25 00:59:24
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @return bool布尔型
*/
public boolean isValidString (String s) {
if (s.length() == 0) {
return true;
}
LinkedList<Integer> leftStack = new LinkedList<>();
LinkedList<Integer> starStack = new LinkedList<>();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (ch == '(') {
leftStack.push(i);
} else if (ch == '*') {
starStack.push(i);
} else if (ch == ')') {
if (!leftStack.isEmpty()) {
leftStack.pop();
} else if (!starStack.isEmpty()) {
starStack.pop();
} else {
return false;
}
}
}
while (!leftStack.isEmpty() && !starStack.isEmpty()) {
if (leftStack.peek() > starStack.peek()) {
return false;
}
leftStack.pop();
starStack.pop();
}
return leftStack.isEmpty();
}
}
发表于 2024-05-02 20:47:15
回复(0)
func isValidString(s string) bool {
var stack []rune = make([]rune, 0)
for i := range s {
switch s[i] {
case '(':
stack = append(stack, '(')
case '*':
stack = append(stack, '*')
case ')':
if len(stack) < 1 {
return false
}
var index int
for index = len(stack) - 1; index >= 0; index-- {
if stack[index] == '(' { //不可能遇到 )
break
}
}
if index >= 0 { //栈中有 (
stack[index] = '*'
}
stack = stack[:len(stack)-1]
}
}
if len(stack) < 0 {
return true
}
//如果stack不为空，则剩余的一定是 ( *
i := len(stack) - 1
for i >= 0 {
if stack[i] == '(' {
if i+1 < len(stack) && stack[i+1] == '*' {
tmp := stack[0:i]
tmp = append(tmp, stack[i+2:]...)
stack = tmp
//i--
} else {
return false
}
}
i--
}
return true
}
发表于 2024-04-24 11:25:59
回复(0)
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param s string字符串
# @return bool布尔型
#
class Solution:
def isValidString(self,s:str) -> bool:
# write code here
class Stack:
def __init__(self) -> None:
self.items = []
def isEmpty(self):
return self.items == []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def size(self):
return len(self.items)
s1 = Stack()
star_list=[]
index, last_index, star_index = 0, 0, 0
pre_index1,pre_index2=0,0
balanced = True
while index < len(s) and balanced:
char = s[index]
if char == '(' :
s1.push(char)
pre_index1=last_index
last_index=max(last_index,index)
elif char == '*':
star_list.append(char)
pre_index2=star_index
star_index=max(star_index,index)
else:
if s1.isEmpty() and star_list == []:
balanced = False
else:
if not s1.isEmpty():
s1.pop()
last_index=pre_index1
else:
star_list.pop()
star_index=pre_index2
index += 1
if s1.isEmpty() and balanced:
return True
elif s1.size()<=len(star_list) and balanced and star_index>=last_index:
return True
else:
return False
编辑于 2024-04-17 12:49:22
回复(0)
import java.util.*;
public class Solution {
/**
* 需要左右两边都遍历
*****( 使用出入栈 单向遍历 是由问题的 *
*
* @param s string字符串
* @return bool布尔型
*/
public boolean isValidString (String s) {
// write code here
int leftNum = 0;
int rightNum = 0;
int xNum = 0;
boolean isCheck = true;
int length = s.length();
char[] chars = s.toCharArray();
for(int i = 0;i< chars.length ; i++){
char c = chars[i];
if(c=='('){
++ leftNum;
}else if(c == ')'){
++ rightNum;
}else{
++ xNum;
}
if(leftNum + xNum < rightNum){
return false;
}
if(rightNum + xNum + (length -1-i) < leftNum){
return false;
}
}
leftNum = 0;
rightNum = 0;
xNum = 0;
for(int i = chars.length -1;i >= 0 ; i--){
char c = chars[i];
if(c=='('){
++ leftNum;
}else if(c == ')'){
++ rightNum;
}else{
++ xNum;
}
if(rightNum + xNum < leftNum){
return false;
}
if(leftNum + xNum + i < rightNum){
return false;
}
}
return isCheck;
}
}
编辑于 2024-04-06 15:41:08
回复(0)
package main
import "fmt"
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @return bool布尔型
*/
func dfs(s string, index int ,count int ,m map[string]bool) bool {
mapKey := fmt.Sprintf("%s_%d_%d",s,index,count)
if _,ok := m[mapKey];ok {
return m[mapKey]
}
if count < 0 {
m[mapKey] = false
return false
}
if index == len(s) {
if count == 0 {
m[mapKey] = true
return true
}else {
m[mapKey] = false
return false
}
}
if s[index] == '(' {
return dfs(s,index+1,count+1,m)
} else if s[index] == ')' {
return dfs(s,index+1,count-1,m)
}else {
for i:=-1;i<=1;i++ {
ret := dfs(s,index+1,count+i,m)
if ret {
m[mapKey] = true
return true
}
}
m[mapKey] = false
return false
}
}
func isValidString( s string ) bool {
// write code here
m := make(map[string]bool)
return dfs(s, 0, 0,m)
}
发表于 2024-03-28 04:26:31
回复(1)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @return bool布尔型
*/
public boolean isValidString (String s) {
// write code here
Deque<Integer> stack1 = new ArrayDeque<>();
Deque<Integer> stack2 = new ArrayDeque<>();
for(int i = 0; i < s.length(); i++) {
switch(s.charAt(i)) {
case '(':
stack1.offerLast(i);
break;
case '*':
stack2.offerLast(i);
break;
case ')':
if(!stack1.isEmpty()) {
stack1.pollLast();
} else {
if(stack2.isEmpty()) return false;
stack2.pollLast();
}
break;
}
}
while(!stack1.isEmpty()) {
if(stack2.isEmpty()) break;
if(stack1.getLast() > stack2.getLast()) break;
stack1.pollLast();
stack2.pollLast();
}
return stack1.isEmpty();
}
}
编辑于 2024-01-14 21:12:46
回复(0)
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param s string字符串
# @return bool布尔型
#
class Solution:
def isValidString(self , s: str) -> bool:
# write code here
stack = []
start_stack = []
for i, char in enumerate(s):
if char == '(':
stack.append(i)
elif char == '*':
start_stack.append(i)
elif char == ')':
if stack:
stack.pop()
elif start_stack:
start_stack.pop()
else:
return False
res = 0
if len(stack) == 0:
return True
else:
# 剩余的未配对的符号中，如果末尾是'('，res == -1，直接返回false
# 因为后进先出，如果pop()没有'*'了，就不可能配对成功了
lst = sorted(stack + start_stack)
while lst:
if len(lst) <= res:
return False
x = lst.pop()
if s[x] == '(':
res += 1
stack.remove(x)
elif s[x] == '*':
if not stack:
res -= 1
else:
return True
return res == 0
# 可是最后一个测试不通过
发表于 2023-08-27 14:30:27
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-10-06 20:49:27 -
2022-10-06 19:32:35
-
2022-09-21 17:52:31
-
2022-09-16 05:48:42
-
2022-09-15 18:52:51
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
