首页 > 试题广场 >

合法的括号字符串

[编程题]合法的括号字符串
  • 热度指数:11437 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个字符串s,字符串s只包含以下三种字符: (,*,),请你判断 s是不是一个合法的括号字符串。合法括号字符串有如下规则:
1.左括号'('必须有对应的右括号')'
2.右括号')'必须有对应的左括号'('
3.左括号必须在对应的右括号前面
4.*可以视为单个左括号,也可以视为单个右括号,或者视为一个空字符
5.空字符串也视为合法的括号字符串

数据范围:

示例1

输入

"()()"

输出

true
示例2

输入

"((*)"

输出

true
示例3

输入

"(*)"

输出

true
示例4

输入

"(((*)"

输出

false
需要正序和倒序遍历两遍,分别把星号当做左括号和右括号。从左往右遍历,把星号视为左括号,在遍历的过程中如果出现左括号数量比右括号数量少就返回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、")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)
我按自己逻辑编写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)
根据能成对的括号不断消除看最后是否只剩星号来判断是否是合法的括号字符串
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 回复(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)
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# 
# @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)
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)
作为一个新手,借鉴了评论区中存放下标的思路,解决某些例如*(() 的匹配问题,可以的,题解和评论区大哥挺多。
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    public boolean isValidString (String s) {
        // write code here
        LinkedList<Integer> list = new LinkedList<Integer>();
        LinkedList<Integer> stars = new LinkedList<Integer>();
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == ')'){ 
                if (list.size() == 0){
                    if(stars.size() > 0){
                        stars.removeFirst();
                    } else {
                        return false;
                    }
                } else {
                    list.removeFirst();
                }

            } else {
                if(s.charAt(i) == '*'){
                    stars.addFirst(i);
                } else 
                    list.addFirst(i);
            }
        }

        //检查
        while(list.size() != 0) {
            if(stars.size() > 0 && stars.getFirst() > list.getFirst()){
                stars.removeFirst();
                list.removeFirst();
            } else {
                return false;
            }
        }
        return true;
    }
}


发表于 2023-07-25 10:24:00 回复(0)
有两个用例一直通过不了,以为是循环结束后星号在(之前这种情况无法匹配,所以做了这种判断,结果第18个用例通过了,第19个又不行,这两个不是矛盾吗?有人知道吗?
发表于 2023-06-22 16:21:57 回复(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)
class Solution:
    def isValidString(self , s: str) -> bool:
        l = []
        star = []
        for i in range(len(s)):
            if s[i] == '(':
                l.append(i)
            elif s[i] == '*':
                star.append(i)
            elif s[i] == ')':
                if l:
                    l.pop()
                elif star:
                    star.pop()
                else:
                    return False
        if len(l) > len(star):
            return False
        i = j = 0
        while l and j < len(star):
            if l[i] < star[j]:
                l.pop(i)
                star.pop(j)
            else:
                j += 1
        if l == []:
            return True
        else:
            return False

发表于 2023-04-10 23:24:08 回复(0)
function isValidString(s) {
    // 左边去查找 右边也去查找 寻找是否符合条件就行
    let left = 0;
    let right = 0;
    let star = 0;
    let flag = true;
    for (let i = 0; i < s.length; i++) {
        if (s[i] === "(") {
            left++;
        } else if (s[i] === ")") {
            right++;
        } else if (s[i] === "*") {
            star++;
        }
        if (left + star < right) {
            flag = false;
            console.log(flag);
            return flag;
        }
    }
    left = 0;
    right = 0;
    star = 0;
    for (let i = s.length - 1; i >= 0; i--) {
        if (s[i] === "(") {
            left++;
        } else if (s[i] === ")") {
            right++;
        } else if (s[i] === "*") {
            star++;
        }
        if (right + star < left) {
            flag = false;
            console.log(flag);
            return flag;
        }
    }
    console.log(flag);
    return flag;
}
发表于 2023-04-03 07:58:34 回复(0)
public boolean isValidString(String s) { char[] chars = s.toCharArray();
    Stack<Integer> left = new Stack<>();
    Stack<Integer> star = new Stack<>(); for (int i = 0; i < chars.length; i++) { if (chars[i] == '(') {
            left.push(i);
        } else if (chars[i] == '*') {
            star.push(i);
        } else { if (left.isEmpty() && star.isEmpty()) { return false;
            } else if (!left.isEmpty()) {
                left.pop();
            } else {
                star.pop();
            }
        }
    } while (!left.isEmpty() && !star.isEmpty()) { if (left.peek() < star.peek()) {
            left.pop();
            star.pop();
        } else { return false;
        }
    } return left.isEmpty();
}
发表于 2023-03-04 12:06:31 回复(0)
/*
借鉴思路:用两个栈分别存储左括号的下标和*的下标(注意是下标,因为要判断左括号在右括号的前面,分别存储能够体现*的灵活性)。
*/
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * @param s string字符串 
     * @return bool布尔型
     */
    public boolean isValidString (String s) {
        Stack<Integer> left = new Stack<>();
        Stack<Integer> start = new Stack<>();
        for(int i=0;i<s.length();i++){
            //左括号或者*号分别入栈
            if(s.charAt(i) == '('){
                left.push(i);
            }
            if(s.charAt(i) == '*'){
                start.push(i);
            }
            //如果是右括号,先从左括号栈中匹配,不满足再从*栈中匹配。
            //匹配:栈不为空,且栈的元素比当前下标小。
            if(s.charAt(i) == ')'){
                if(!left.isEmpty() && left.peek()<i){
                    left.pop();
                }else{
                    if(!start.isEmpty() && start.peek()<i){
                        start.pop();
                    }else{
                        return false;
                    }
                }
            }
        }
        //再判断左括号的栈是否为空,用*进行匹配。
        while(!left.isEmpty() && !start.isEmpty()){
                if(left.peek() < start.peek()){
                    left.pop();
                    start.pop();
                }else{
                    return false;
                }
        }
        //如果左括号的栈为空,则合格;否则不合格。
        if(left.isEmpty()){
            return true;
        }else{
            return false;
        }
    }
}


发表于 2023-02-20 10:40:51 回复(0)
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @return bool布尔型
#
class Solution:
    def isValidString(self , s: str) -> bool:
        # write code here
        
        #定义2个空栈,一个用来存放左括号,一个用来存放*号,遇到右括号的时候先出stack1,当stack1为空的时候,再出stack2,当stack2为空的时候,返回False
        #print("ok")
        stack1=[]
        stack2=[]
        #print(s)
        for x in range(len(s)):
            if s[x] == "(":
                stack1.append(x)
            elif s[x]=="*":
                stack2.append(x)
            elif s[x]==")":
                if len(stack1)>0:
                    stack1.pop()
                elif len(stack2)>0:
                    stack2.pop()
                else:
                    return False
        print(stack1)
        print(stack2)
    #如果比较完,stack1等于0的话,说明括号已经完全匹配了,返回true即可
        if len(stack1) ==0:
            return True
    

    #如果说stack1大于0,并stack2大于0.stack1的元素比stack2多,需要比较stack1中的括号的位置与*的索引顺序,小于*Hao的索引才能匹配,大于星号则永远不能匹配,当stack1中的元素pop完退出while循环或者当stack1中的元素的pop值比stack2还大,需要将pop出的元素append回来直接break出循环体,最后通过比较stack1中的元素数量如果为空了,就匹配成功了说明,否则匹配失败
        elif len(stack1)>0 and len(stack2)>0 and len(stack1)<=len(stack2) :
            while len(stack1)>0  : 
                x=int(stack1.pop())
                y=int(stack2.pop())
                print(stack1,x,y)
                if x<y:
                    pass              
                else:
                    stack1.append(x)
                    break
            print(stack1)       
            if  len(stack1) ==0:
                return True      
            else:
                return False
        else:
            return False
        

发表于 2023-02-17 12:24:23 回复(0)
class Solution:
    def isValidString(self , s: str) -> bool:
        # 从左往右遍历,把*当成左括号,发现左括号仍比右括号少时,说明不合法
        res = []
        for i in s:
            if i == "(" or i == "*":
                res.append(i)
            else:
                try:
                    res.pop()
                except:
                    return False
        # 从右往左遍历,把*当成右括号,发现右括号仍比左括号少时,说明不合法
        ans = []
        for i in s[::-1]:
            if i == ")" or i == "*":
                ans.append(i)
            else:
                try:
                    ans.pop()
                except:
                    return False
        return True
发表于 2022-09-02 18:10:12 回复(0)
括号匹配的的关键:在从左到右遍历字符串的时候,对于每一个右括号,左边都有至少1个左括号供消耗;最终结束时,左括号至少可以为0个。对于*号,分别计算其可以形成至多和至少多少个左括号就行了。
发表于 2022-09-02 14:56:20 回复(0)
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @return bool布尔型
#
class Solution:
    def isValidString(self , s: str) -> bool:
        # write code here
        left = []
        star =[]
        s = s[1:-1]
        # 把所有(和*当左边界压入栈
        for i in range(len(s)):
            if s[i] == '(':
                left.append(i)
            elif s[i] == '*':
                star.append(i)
            else:
                # )右括号出栈
                if len(left):
                    left.pop()
                elif len(star):
                    star.pop()
                # 右括号不够匹配了,返回false
                else:
                    return "false"
        # 然后右括号匹配
        while len(left) and len(star):
            if len(left)>len(star):
                return "false"
            if left.pop() > star.pop():
                return "false"
        return "true"
        

print(Solution().isValidString(input()))
翻译过来的为啥输出不通过
发表于 2022-08-07 13:00:40 回复(0)