提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  数据库

当前栏目

20. 有效的括号

数据
2023-04-18 16:11:28 时间

思路：

1，这里利用了一个与运算排除所有奇数长度字符串 2，利用栈来回显前一个元素，每次栈不为空，我们再次入栈时候判断下括号是否成对即可，另外因为我们是拿后面元素和前面元素匹配，因此要注意peek拿的是左括号，当前字符应该是右括号

代码：

    class Solution {
        public boolean isValid(String s) {
            //如果长度是奇数
            if ((s.length() & 1) == 1) {
                return false;
            }
            //向栈内加数据相同的取数据
            Stack<Character> stack = new Stack<Character>();
            for (char c : s.toCharArray()) {
                if (stack.isEmpty()) {
                    stack.push(c);
                } else {
                    if (equalCheck(c, stack.peek())) {
                        stack.pop();
                    } else {
                        stack.push(c);
                    }
                }
            }
            return stack.isEmpty();
        }

        private boolean equalCheck(char c, Character peek) {
            return c == ')' && peek == '('
                    || c == ']' && peek == '['
                    || c == '}' && peek == '{';
        }
    }

也有人用hash先存了值，进行匹配，咱们也写下这种写法

class Solution {
        public boolean isValid(String s) {
            Map<Character,Character> map=new HashMap<Character,Character>(8) {
                {
                    put(')','(');
                    put(']','[');
                    put('}','{');
                }
            };

            //如果长度是奇数
            if ((s.length() & 1) == 1) {
                return false;
            }
            //向栈内加数据相同的取数据
            Stack<Character> stack = new Stack<Character>();
            for (char c : s.toCharArray()) {
                if (stack.isEmpty()) {
                    stack.push(c);
                } else {
                    if (stack.peek().equals(map.get(c))) {
                        stack.pop();
                    } else {
                        stack.push(c);
                    }
                }
            }
            return stack.isEmpty();
        }
    }

不过貌似结果并不如何，快的是第一种

相关文章