小东Freeman + 关注

签名:我们爱我们的倒霉工作,也爱这千疮百孔的世界。

有效的括号算法详解

发表于 5个月前   839次查看    1评论  4 赞

题目:

给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。

有效字符串需满足:

1、左括号必须用相同类型的右括号闭合。

2、左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

事例:

输入: "()"
输出: true

输入: "()[]{}"
输出: true

输入: "(]"
输出: false

输入: "([)]"
输出: false

输入: "{[]}"
输出: true


解题思路:

  1. 初始化栈 S。

  2. 一次处理表达式的每个括号。

  3. 如果遇到开括号,我们只需将其推到栈上即可。这意味着我们将稍后处理它,让我们简单地转到前面的 子表达式

  4. 如果我们遇到一个闭括号,那么我们检查栈顶的元素。如果栈顶的元素是一个 相同类型的 左括号,那么我们将它从栈中弹出并继续处理。否则,这意味着表达式无效。

  5. 如果到最后我们剩下的栈中仍然有元素,那么这意味着表达式无效。


代码:

class Solution {
    public boolean isValid(String s) {
        if(s.equals(""))
            return true;
        Stack<Character> x=new Stack<Character>();
        char popword;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='('||s.charAt(i)=='['||s.charAt(i)=='{')
                x.push(s.charAt(i));
            else{
                if(!x.empty()){
                popword=x.pop();
                if(!((popword=='('&& s.charAt(i)==')')||(popword=='['&& s.charAt(i)==']')||(popword=='{'&& s.charAt(i)=='}')))
                    return false;
                else{
                    if(i==s.length()-1&&(x.empty()))
                        return true;}
                }
                else
                    return false;
            }
        }
        return false;   
    }
}


用时:10ms

4人已赞


本文由Fun言网 – 小东Freeman创作,转载请务必附上本文链接和出处,欢迎参与我们的付费投稿计划


你还没有登录,请先 登录注册!
文章评论1