我要招人

去企业版

首页 > 试题广场 >

合法的括号字符串

[编程题]合法的括号字符串

热度指数：12172 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个字符串s，字符串s只包含以下三种字符: (，*，)，请你判断 s是不是一个合法的括号字符串。合法括号字符串有如下规则:

1.左括号'('必须有对应的右括号')'

2.右括号')'必须有对应的左括号'('

3.左括号必须在对应的右括号前面

4.*可以视为单个左括号，也可以视为单个右括号，或者视为一个空字符

5.空字符串也视为合法的括号字符串

数据范围:

$1<=s.length<=100$

示例1

输入

"()()"

输出

true

示例2

输入

"((*)"

输出

true

示例3

输入

"(*)"

输出

true

示例4

输入

"(((*)"

输出

false

算法知识视频讲解

Java

牛客148901号

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)

Java

呸，看见你就开心

借鉴思路：用两个栈分别存储左括号的下标和*的下标（注意是下标，因为要判断左括号在右括号的前面，分别存储能够体现*的灵活性）。

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)

Java

blue&&lan

可能出现错误的情况只有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)

Java

牛客196305255号

public boolean isValidString (String s) {
        Deque<Integer> de1=new LinkedList<>();
		Deque<Integer> de2=new LinkedList<>();
		 for(int i=0;i<s.length();i++) {
			 char c=s.charAt(i);
			 if(c=='(')
				 de1.push(i);
			 else if(c=='*')
				 de2.push(i);
			 else {
				 if(de1.size()>0) {
					 de1.pop();
				 }else if(de2.size()>0) {
					 de2.pop();
				 }else {
					 return false;
				 }
			 }
		 }
		 if(de1.size()>de2.size())
             return false;
		 while(de1.size()>0) {
			 if(de1.pop()>de2.pop())
				 return false;
		 }
		 return true;
    }

发表于 2022-01-14 16:47:11 回复(0)

Java

pein531

需要正序和倒序遍历两遍，分别把星号当做左括号和右括号。从左往右遍历，把星号视为左括号，在遍历的过程中如果出现左括号数量比右括号数量少就返回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)

提交观点

问题信息

贪心动态规划字符串栈

上传者：牛客301499号

难度：

6条回答 154收藏 6178浏览

通过挑战的用户

查看代码

牛客70179...

2022-10-06 20:49:27
Koning

2022-10-06 19:32:35
牛客76427...

2022-09-21 17:52:31
牛客71137...

2022-09-16 05:48:42
老年Jime

2022-09-15 18:52:51

合法的括号字符串

输入

输出

输入

输出

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题