LeetCode-简单-20-有效的括号(Java)

学了东西就要练,先用简单的题来练练java。
上面这句话早就该说了,但是因为有东西要提前发,所以这篇文章被延后了,本来应该是第一篇Java的LeetCode题的。

题目

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

有效字符串需满足:

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

输入: “()”
输出: true
示例 2:

输入: “()[]{}”
输出: true
示例 3:

输入: “(]”
输出: false
示例 4:

输入: “([)]”
输出: false
示例 5:

输入: “{[]}”
输出: true

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

用栈的思想来解决。
即:按顺序读入字符,碰到右括号,则对比前面是否是匹配的左括号,是则消除。

可以确定的一点,正确的括号组合,一定会出现左右括号在一起的情况,即()一定会出现。
而剩余没有并在一起的,必然是被若干个并在一起的括号隔开。
例如,( ( ( [] [] ) {} ) )
将合并的三个黑色的括号对删去,可以得到:( ( () ) ),再删去内部的括号,以此类推,正确的括号组合将被删完。

使用栈的思想很容易进行这种处理,只要按顺序读入字符,碰到合并起来的括号对,就删除,就可以解决这个问题。

而非法的情况也很简单:
出现了右括号,但右括号的左边不是匹配的左括号,必然是错误的括号组合。
出现了右括号,但右括号左边没有字符,即此时栈为空。

两种非法的情况都可以看做:出现右括号时,对左边字符的比对。
但考虑到栈为空时,新入栈的右括号左边没有任何元素,会造成错误,因此这个判断需要换成对栈大小的判断。

代码

class Solution {
    public boolean isValid(String s) {
        int i;
        String tempS = "";
        for(i=0;    i<s.length();   i++){
            switch (s.charAt(i)){
                case '(':
                case '[':
                case '{':
                	tempS = tempS + s.charAt(i);
                    break;
                case ')':
                	if(tempS.length()!=0 && tempS.charAt(tempS.length()-1) == '(') tempS = tempS.substring(0, tempS.length()-1);
                    else return false;
                	break;
                case ']':
                	if(tempS.length()!=0 && tempS.charAt(tempS.length()-1) == '[') tempS = tempS.substring(0, tempS.length()-1);
                    else return false;
                	break;
                case '}':
                    if(tempS.length()!=0 && tempS.charAt(tempS.length()-1) == '{') tempS = tempS.substring(0, tempS.length()-1);
                    else return false;
                    break;
            }
        }
        if ("".contentEquals(tempS)) return true;
        return false;
    }
}

You may also like...

发表评论

邮箱地址不会被公开。 必填项已用*标注