首页 > 试题广场 >

有效的括号字符串

[编程题]有效的括号字符串
  • 热度指数：1816 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：
  1. 任何左括号 ( 必须有相应的右括号 )。
  2. 任何右括号 ) 必须有相应的左括号 ( 。
  3. 左括号 ( 必须在对应的右括号之前 )。
  4. * 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
  5. 一个空字符串也被视为有效字符串。
示例1

输入

"()"

输出

true
示例2

输入

"(*)"

输出

true
示例3

输入

"(*))"

输出

true

备注:
字符串大小将在 [1，100] 范围内。

算法知识视频讲解
添加回答
励志要变胖的人头像 励志要变胖的人
双向遍历
1.正向遍历：正向遍历中将‘*’看作'('，遍历过程中遇到右括号就将左括号数量减1，如果左括号数量小于0，则说明把*号都看做'('也不能完成匹配。如果遍历结束左括号数量一直保持大于等于0，则说明有可能可以完成匹配，为什么是有可能呢，因为你不知道剩下的左括号有多少是*号变的，有多少是原本的左括号，无法确定剩下部分是否有效（如果左括号数量等于右括号数量，剩下的左括号全是*号变的；如果小于，剩下的也是*号变的；如果大于，则是混合的，此时需要看反向遍历的结果，因为此时*全部用来匹配左括号或看为空字符）。
2.反向遍历：类似正向遍历，将‘*’看作')'，如果左括号数量小于0，不能完成匹配；如果遍历结束右括号数量大于等于零，则说明有可能完成匹配，理由类似正向遍历。
思考上面提到混合的情况：如果正向和反向遍历的结果结果都是大于等于0的，该字符串是有效的，为什么呢，先看正向遍历，最后剩下的是*号变成的左括号和真正的左括号，我们现在再把*号变回来，如果此时左括号和*号可以完成匹配，那么该字符串一定是有效的，怎么保证可以完成匹配呢，反向遍历的结果保证了可以完成匹配，因为反向遍历就是将‘*’看作')'匹配左括号的过程，反向遍历保证。 
class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    bool checkValidString(string s) {
        // write code here
        int l=0,r=0;
        for(int i=0;i<s.length();i++){
            l+=s[i]==')'?-1:1;
            r+=s[s.length()-1-i]=='('?-1:1;
            if(l<0||r<0)
                return false;
        }
        return true;
    }
};
编辑于 2021-04-05 13:25:13 回复(1)
Lazyzzzz头像 Lazyzzzz 
import java.util.*;


public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    public boolean checkValidString(String s) {
        // write code here
        Stack<Integer> stars = new Stack<>();
        Stack<Integer> stack = new Stack<>();
        char[] chs = s.toCharArray();
        for(int i = 0;i<chs.length;i++) {
            char ch = chs[i];
            if (ch == '(') {
                stack.push(i);
            } else if (ch == '*') {
                stars.push(i);
            } else if (ch == ')') {
                if (stack.isEmpty() && stars.isEmpty()) {
                    return false;
                } else if (!stack.isEmpty()) {
                    stack.pop();
                } else if (!stars.isEmpty()) {
                    stars.pop();
                }
            }
        }
        if (stack.size() > stars.size()) {
            return false;
        } else {
            while(!stack.isEmpty() && !stars.isEmpty()) {
                int x = stack.pop();
                int y = stars.pop();
                if (y < x) {
                    return false;
                }
            }
            return stars.size() >= 0;
        }
    }
}

发表于 2021-03-18 16:04:32 回复(0)
年华追梦头像 年华追梦 
class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    bool checkValidString(string str) {
        deque<int> lp,k;
        for(int i=0;i<str.size();i++){
            if(str[i]=='(') lp.push_back(i);//'('的个数
            if(str[i]=='*') k.push_back(i);//'*'的个数
            if(str[i]==')') {
                if(lp.empty()&&k.empty()){
                    return false;
                }else if(!lp.empty()){
                    lp.pop_back();
                }else if(!k.empty()){
                    k.pop_front();
                }
            }
        }
        if(k.size()<lp.size()){
            return false;
        }
        while(!lp.empty()){
            //cout<<k.front()<<" "<<lp.front()<<endl;
            while(!k.empty()&&lp.front()>k.front()) k.pop_front();
            if(lp.size()>k.size()) return false;
            k.pop_front();lp.pop_front();
        }
        return true;
    }
};
这道题关键部分是‘*’字符，它可以转变任意字符，因此先考虑"()"括号匹配成功的情况，最后再考虑剩余的'*'，还有剩余的‘(’或者‘)’，左括号或右括号最终只能剩余一种或者都没有。因此利用deque容器存储各个字符的位置，为了后面判断剩余的字符是否符合匹配原则，比如剩余"***((("，很明显'*'字符优先于'('，这种情况也不会匹配成功。首先声明两个deque容器，lp，k分别存储'('和'*'字符的所在字符串中的位置，然后枚举每次插入，若找到一个')'，这时候就开始匹配，优先考虑lp存储的左括号，而且是最近的那个左括号，即为lp末端的，然后再考虑k容器的'*'。至于为什么要优先考虑'*'的最前面的元素，是为了最后只剩余'('左括号进行比较，让'*'尽可能在'('的右边，这样才能匹配成功。字符串枚举完成后，然后对lp和k容器进行比较，只需要比较它们出现先后顺序与剩余元素的个数即可。
发表于 2021-03-14 11:53:14 回复(0)
pein531头像 pein531
用栈求解，先把星号当成左括号，用它和左括号去抵消右括号。如果还有剩余的星号和左括号，就将星号作为右括号去抵消左括号，由于星号可以为空，因此抵消完左括号后，无论星号是否有剩余都可以。 
class Solution:
    def checkValidString(self , s ):
        # write code here
        stack = []
        stars = []
        for i, c in enumerate(s):
            if c == '(':
                stack.append(i)
            elif c == '*':
                stars.append(i)
            elif c == ')':
                # 先用星号和左括号去平衡右括号
                if not stack and not stars:
                    return False
                elif stack:
                    stack.pop()
                elif stars:
                    stars.pop()
        # 剩下的星号只能当右括号或者空
        if len(stack) > len(stars):
            return False       # 此时剩下的左括号无法被星号平衡完
        else:
            while stack and stars:
                i, j = stack.pop(), stars.pop()
                # 此时星号要中和掉左括号的话其位置必须在左括号右边
                if i > j:
                    return False
            # 星号可以为空，允许没有中和完
            return len(stars) >= 0

发表于 2021-07-23 21:09:43 回复(0)
C/C++
ZeRo1.头像 ZeRo1.
class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    bool checkValidString(string s) {
        int n = s.size();
        stack<int> star;
        stack<int> left;
        for (int i = 0; i < n; ++i) {
            if (s[i] == '(') left.push(i);
            else if (s[i] == '*') star.push(i);
            else {
                if (star.empty() && left.empty()) return false;
                if (!left.empty()) left.pop();
                else star.pop();
            }
        }
        while (!left.empty() && !star.empty()) {
            if (left.top() > star.top()) return false;
            left.pop(); star.pop();
        }
        return left.empty();
    }
};
发表于 2021-07-04 17:35:27 回复(0)
球球大厂收了我吧头像 球球大厂收了我吧 
import java.util.*;


public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
      public boolean checkValidString (String s) {
        int n =s.length();
        boolean [][]dp=new boolean[n][n];
        //basecase
        for (int i = 0; i < n; i++) {
            if (s.charAt(i)=='*'){
                dp[i][i]=true;
            }
        }
        for (int i = 0; i < n-1; i++) {
            if ((s.charAt(i)=='('||s.charAt(i)=='*')&&(s.charAt(i+1)=='*'||s.charAt(i+1)==')')){
                dp[i][i+1]=true;
            }
        }
        for (int i = n-3; i >=0; i--) {
            for (int j = i+2; j < n; j++) {
                char l=s.charAt(i);
                char r=s.charAt(j);
                if( (l=='*'||l=='(')&&(r=='*'||r==')') ){
                    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];
                }
            }
        }
        return dp[0][n-1];
    }
}
动态规划 求party 拽拽
发表于 2022-07-29 09:39:19 回复(0)
wonderson头像 wonderson
双栈，栈记录左括号和*的下标，右括号优先匹配左括号，再匹配星号。
最后将多余的左括号与后面的星号做匹配。 
import java.util.*;


public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    public boolean checkValidString (String s) {
        char[] cs = s.toCharArray();
        int n = cs.length;

        int[] left = new int[n], star = new int[n];
        int li = -1, si = -1;

        for (int i = 0; i < n; i++) {
            if (cs[i] == '(') {
                left[++li] = i;
            } else if (cs[i] == '*') {
                star[++si] = i;
            } else {
                if (li >= 0) {
                    li--;
                } else if (si >= 0) {
                    si--;
                } else {
                    return false;
                }
            }
        }

        while (li >= 0) {
            if (si < 0 || star[si] < left[si]) {
                return false;
            }
            si--;
            li--;
        }
        return true;
    }
}


发表于 2022-03-28 10:04:25 回复(0)
Java
talkingCoder头像 talkingCoder 
import java.util.*;
public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    public boolean checkValidString (String s) {
        if(s.length() == 0) return true;
        Queue q1 = new LinkedList();
        Queue q2 = new LinkedList(); 
        for(int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == '(') q1.offer(i);
            else if(s.charAt(i) == '*') q2.offer(i);
            else {
                if(!q1.isEmpty()) q1.poll(); // 只要左右括号对等，那么用哪个 `(` 匹配（包括 `*` 转化的）都是可以的
                else if(!q2.isEmpty()) q2.poll(); // 删除最前面的 `*`，增大 `*` 匹配 `(` 可能性
                else return false; // 没有可匹配的 `(`
            }
        }
        while(!q1.isEmpty()) {
            while(!q2.isEmpty() && q2.peek() < q1.peek()) { // 最左边 `*` 位置若不在 `(` 右边
               q2.poll();
            }
            if(q2.isEmpty()) return false;
            q1.poll(); // `*` 当作右括号，匹配上啦 
        }
        return true;
    }
}
编辑于 2021-07-19 17:04:04 回复(0)
fizzfrank头像 fizzfrank
这道题可以使用DFS完成，既然*可以替换成其他，那么我一一替换 
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();
        System.out.println(new Main().checkValidString(str));
    }
    /**
     *
     * @param s string字符串
     * @return bool布尔型
     */
    // 暴力替换
    public boolean checkValidString (String s) {
        if (s == null || s.length() == 0) {
            return true;
        }

        char[] chars = s.toCharArray();
        return dfs(chars, 0, chars.length - 1);
    }

    // bug 的原因 每次减1, 都要判断一次
    int stackCount = 0;
    boolean dfs (char[] chars, int start, int end) {
        if (start > end) {
            return stackCount == 0;
        }

        char ch = chars[start];
        int tmp;

        if (ch == '(') {
            stackCount++;
            return dfs(chars, start + 1, end);
        }

        if (ch == ')') {
            stackCount--;
            if (stackCount < 0) {
                return false;
            }
            return dfs(chars, start + 1, end);
        }

        tmp = stackCount;

        // 当作(
        stackCount++;
        boolean result = dfs(chars, start + 1, end);

        if (result) { // 匹配，不再向下
            return true;
        }

        // 否则，回說
        stackCount = tmp;

        // 当作)
        stackCount--;
        if (stackCount < 0) {
            return false;
        }
        result = dfs(chars, start + 1, end);
        if (result) {
            return true;
        }

        stackCount = tmp;
        // 当作*
        result = dfs(chars, start + 1, end);
        if (result) {
            return true;
        }

        return false;
    }
}


发表于 2021-07-17 22:09:55 回复(0)
有一个地方.头像 有一个地方.
区间dp
dp[i][j] s[i:j]是否有效 
#
# 
# @param s string字符串 
# @return bool布尔型
#
class Solution:
    def checkValidString(self , s ):
        # write code here
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        for i in range(n):
            if s[i] == '*':
                dp[i][i] = True
        # x - i + 1= length
        for length in range(2, n + 1):
            for i in range(n):
                if i + length - 1 <= n - 1:
                    if length == 2:
                        if s[i] in ['(', '*'] and s[i + 1] in [')', '*']:
                            dp[i][i + 1] = True
                    else:
                        if s[i] in ['(', '*'] and s[i + length - 1] in [')', '*'] and dp[i + 1][i + length - 2]:
                            dp[i][i + length - 1] = True
                        for k in range(i, i + length - 1):
                            dp[i][i + length - 1] = (dp[i][k]&dp[k + 1][i + length - 1])|dp[i][i + length - 1]
        return dp[0][n - 1]

sol = Solution()
print(sol.checkValidString("(*)"))


发表于 2021-07-10 12:05:56 回复(0)
Python
卡瓦夏日头像 卡瓦夏日 
class Solution:
    def checkValidString(self , s ):
        res=[]
        for i in s:
            if i=='('&nbs***bsp;i=='*':
                res.append(i)
            else:
                j=1
                while j<=len(res) and res[-j]!='(':
                    j+=1
                if j<=len(res):
                    del res[-j]
                elif len(res)!=0:
                    res.pop()
                elif len(res)==0:
                    return False
        r=[]#stack for *
        i=0
        for i in range(len(res)-1,-1,-1):
            if res[i]=="*":
                r.append(res[i])
            else:
                if len(r)>0 and r[-1]=="*":
                    r.pop()

                else:
                    return False
        if '(' not in r:
            return True

发表于 2021-04-19 21:11:33 回复(0)
煎饼果子w头像 煎饼果子w

双向一轮遍历法 

import java.util.*;


public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    public boolean checkValidString (String s) {
        // write code here
        if (s == null || s.length() == 0) {
            return true;
        }

        char[] sc = s.toCharArray();
        int n = sc.length;
        int left = 0, right = 0;
        for (int i = 0; i < n; ++i) {
            //从左向右
            left += sc[i] == ')' ? -1 : 1;
            //从右向左
            right += sc[n - 1 - i] == '(' ? -1 : 1;
            if (left < 0 || right < 0)
                return false;
        }
        return true;
    }
}


发表于 2021-03-26 21:22:54 回复(0)
Python
牛客198789950号头像 牛客198789950号
class Solution:
    def checkValidString(self , s ):
        # write code here
        T=['s']
        for i in s:
            if i=='(' or i=='*':
                T.append(i)
            elif i==')':
                kk=len(T)-1
                while T[kk]=='*':
                    kk-=1
                if kk==0:
                    T.pop()
                else: T.pop(kk)
            if len(T)<1: break
        if len(T)<1: return False
        if T.count('(') >T.count('*')+1 or T[-1]=='(': return False
        else: return True
发表于 2021-03-24 22:49:13 回复(0)
不偷不抢安度因_头像 不偷不抢安度因_ 
class Solution {
public:
    bool checkValidString(string str) {
        stack<int> left, s;
        for (int i = 0; i < str.size(); ++i) {
            if (str[i] == '(') {
                left.push(i);
            } else if (str[i] == '*') {
                s.push(i);
            } else {
                if (!left.empty()) {
                    left.pop();
                } else if (!s.empty()) {
                    s.pop();
                } else {
                    return false;
                }
            }
        }
 
        while (!left.empty() && !s.empty()) {
            if(left.top() > s.top()) {
                return false;
            }
            left.pop();
            s.pop();
        }
 
        return left.empty();
    }
};

发表于 2021-03-22 22:08:55 回复(0)
雷诺诺头像 雷诺诺 
变成’（‘从左往右匹配’）‘再变成’）‘从右往左匹配’（‘



          int left = 0;
        int right = 0;
        for(int i=0;i<s.length();i++){
            if(s[i]=='('||s[i]=='*') left++;
            else left--;
            if(left<0)  return false;
        }
        for(int i=s.length()-1;i>=0;i--){
            if(s[i]==')'||s[i]=='*') right++;
            else right--;
            if(right<0)  return false;
        }
        return true;

发表于 2021-03-18 00:20:11 回复(1)
JavaScript
_______struggle゛头像 _______struggle゛ 
function checkValidString( s ) {
    const arrStack = []
    for (let i = 0; i < s.length; i++) {
        let anyVal = s[i]
        if (anyVal === "*") arrStack.push("*")
        if (anyVal === "(") arrStack.push("(")
        if (anyVal === ")") {
            if (arrStack.length === 0) return false
            let numStarIndex = -1
            for (let j = arrStack.length - 1; j > -1; j--) {
                if (arrStack[j] === "(") {
                    arrStack.splice(j, 1)
                    break
                }
                if (arrStack[j] === "*" && numStarIndex === -1) numStarIndex = j
            }
            if (numStarIndex !== -1) arrStack.splice(numStarIndex, 1)
        }
    }
    let numTmp = Math.floor(arrStack.length / 2)
    for (let i = 0; i < numTmp; i++) {
        let anyLeft = arrStack[i]
        let anyRight = arrStack[arrStack.length - i - 1]
        if (anyLeft === "(" && anyRight === "*") {
            arrStack[i] = "*"
        }
        if (anyLeft === "*" && anyRight !== ")") {
            arrStack[arrStack.length - i - 1] = "*"
        }
    }
    if (arrStack.length !== 0) {
        return !(arrStack.indexOf("(") !== -1 || arrStack.indexOf(")") !== -1);
    }
    return true
}

发表于 2021-03-10 12:02:39 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 游戏研发工程师 2021 数据库工程师 测试开发工程师 虾皮信息 大数据开发工程师 Java工程师
上传者：小小
难度：
16条回答 4344浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号