首页 > 试题广场 > 有效的括号字符串
[编程题]有效的括号字符串
  • 热度指数:1415 时间限制: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)
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)
用栈求解,先把星号当成左括号,用它和左括号去抵消右括号。如果还有剩余的星号和左括号,就将星号作为右括号去抵消左括号,由于星号可以为空,因此抵消完左括号后,无论星号是否有剩余都可以。
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)
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) {
        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)
这道题可以使用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)
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)

双向一轮遍历法

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)
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)
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)

热门推荐

通过挑战的用户