首页 > 试题广场 >

有效的括号字符串

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

输入

"()"

输出

true
示例2

输入

"(*)"

输出

true
示例3

输入

"(*))"

输出

true

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

算法知识视频讲解
添加回答
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)
提交观点

问题信息

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

热门推荐

通过挑战的用户

相关试题

有效的括号字符串

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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