LeetCode-有效的括号(java实现)

爱被打了一巴掌 2022-05-18 09:55 170阅读 0赞

题目如下：

![70][]

刚看到这题的时候，还是非常简单的想暴力解决。暴露了眼界还是太狭隘。刚开始的想法是只要判断出"()\{\}\[\]"、"(\{\[\]\})"、"()"...等这样为true的情况应该就能解决问题了。但是想法太简单 ，运行的结果不是忘了判断这种情况就是忘了判断那种情况，最后运算还超时了。

后来在网上找了一下代码，运行时间为14ms。这段代码运用了栈stack，这是以前的知识盲区。整体的思路是这样的：例如我们需要判断如下字符串“\{\[\]\}”，把字符串的第一个字符压入栈，然后用字符串的后一个字符与之相比较。如果不相同，则把这个字符也压入栈。第二次for循环，此时stack.peek()取到的是‘\[’, s.charAt(i) == '\]'。此时根据if中的判断条件，表达式为true，stack把栈顶元素弹出。此时stack中还剩下一个元素‘(’，进入下一次for循环，stack.peek()取值是')'，再次进入循环判断。

代码如下：

public boolean isValid(String s) {
            if(s == "" || s.length() == 0)
                return true;
    
            Stack stack = new Stack();
            stack.push(s.charAt(0));
    
            for(int i=1; i<s.length(); i++){
                if(!stack.isEmpty()){
                    if(stack.peek().equals((char)(s.charAt(i)-1)) || stack.peek().equals((char)(s.charAt(i)-2))){
                        stack.pop();
                    }else {
                        stack.push(s.charAt(i));
                    }
                }else {
                    stack.push(s.charAt(i));
                }
            }
    
            if(stack.isEmpty())
                return true;
    
            return false;

运行成功之后，看到一个实现代码，同样是运用了stack。但是运行时间只有6ms，相差了快3倍。遂好好把玩了一番，不得感叹，喵啊~ 具体思路就不啰嗦了，代码表达的非常清晰

public boolean isValid(String s) {
    
            Stack<Character> stack = new Stack<>();
    
            for (int i = 0; i < s.length(); i++){
                char ch = s.charAt(i);
                if(ch == '(' || ch == '[' || ch == '{'){
                    stack.push(ch);
                }else{
                    if(stack.isEmpty()){
                        return false;
                    }
    
                    char topChar = stack.pop();
                    if(ch == ')' && topChar != '('){
                        return false;
                    }else if(ch == ']' && topChar != '['){
                        return false;
                    }else if(ch == '}' && topChar != '{'){
                        return false;
                    }
                }
            }
    
            return stack.isEmpty();
        }

[70]: /images/20220518/b5c0d67e20724ca1900afbf9531fe468.png