LeeCode 20题：有效的括号

小半 • 2023年2月3日上午10:55 • 技术随笔 • 阅读 100

链接：LeeCode 20
题目：
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例：
输入：s = “{[]}”
输出：true

输入：s = “([)]”
输出：false

方法一：使用辅助栈和HashMap
思路：
用HashMap放入成对的括号，由于要用get()方法通过右括号得到对应的左括号，所以右括号为 key ，左括号为value；
遍历输入的String，左括号则压栈；
如果是右括号，当栈不为空，&& 栈顶peek() = 右括号对应的左括号才弹出！ 否则 return false

class Solution {
    public boolean isValid(String s) {
        if(  (s.length()%2)!=0   ){ //非成对即余数不为0，则直接false
            return false;
        }

        Map<Character,Character> m=new HashMap<>(); 
        //要用get方法，通过右括号找左括号，所以key放右括号，value放左括号！
        m.put(')','(');
        m.put('}','{');
        m.put(']','[');

        Stack<Character> stack=new Stack<>(); //栈
        for(int i=0;i<s.length();i++){
            //转换为字符
            char c=s.charAt(i);
            if(m.containsValue(c)){ //如果是左括号，压栈
                stack.push(c);
            }else if(m.containsKey(c)){ //如果是右括号,比较
                if( !stack.isEmpty() && stack.peek()==m.get(c)){ //栈不为空，且栈顶=右括号对应的左括号才弹出！ 否则 return false
                    stack.pop();
                }else{
                	return false; 
                }
            }else{ // 如果都不是，直接false
				return false;
			}
        }
        return stack.isEmpty(); //栈为空则true，不为空则false
    }
}

注意;此处必须是右括号和栈顶成对，这样才满足括号以正确的顺序闭合，如：“([)]” 是错误的，未按正确的顺序闭合。

如果是成对的括号，那么遍历到右括号时，栈顶一定是对应类型的左括号！

简化：

class Solution {
    public boolean isValid(String s) {
        //
        HashMap<Character,Character> h=new HashMap<>();
        h.put(')','(');
        h.put('}','{');
        h.put(']','[');

        Stack<Character> stack=new Stack<>();
        //

        for(int i=0;i<s.length();i++){
            Character c=s.charAt(i);
            // left
            if(h.containsValue(c)){
                stack.push(c);
            }else{  // right
                if(!stack.isEmpty() && h.get(c)==stack.peek()){
                    stack.pop();
                }else{
                    return false;
                }

            }
        }

        return stack.isEmpty();
    }
}

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/89378.html

LeeCode 20题：有效的括号

相关推荐