LeetCode(20)判断字符串合法括号

清疚 2022-05-12 19:28 144阅读 0赞

问题

Given a string containing just the characters `'('`, `')'`, `'{'`, `'}'`, `'['` and `']'`, determine if the input string is valid.

An input string is valid if:

1.  Open brackets must be closed by the same type of brackets.
2.  Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

解决，考虑使用栈的先进后出特性来存放这个字符串。将字符串中字符从头开始入栈，如果栈空，则直接入栈。如果非空，则判断栈顶字符。根据不同的情况，判断是否与当前字符与栈顶字符是否构成一个完整的括号。如果是，则栈顶出栈，如果不是，则当前字符入栈。最后，返回栈是否非空，空，表明是合法括号字符串；非空，则有多余的字符不够成合法括号字符串。注意，对于参数的特性情况的判断。

java解决

class Solution {
        public boolean isValid(String s) {
            // 参数合法性判断
            if(s == null){
                return false;
            }
            int size = s.length();
            if (size < 1 || s.equals("")) {
                return true;
            }
            // 以链表作为栈
            LinkedList<Character> stack = new LinkedList<Character>();
            for (int i = 0; i < size; i++) {
                char tmp = s.charAt(i);
                if (stack.size() == 0) {
                    stack.push(tmp);
                } else {
                    char top = stack.getFirst();
                    if (top == '(') {
                        if (tmp == ')') {
                            stack.pop();
                        } else {
                            stack.push(tmp);
                        }
                    } else if (top == '[') {
                        if (tmp == ']') {
                            stack.pop();
                        } else {
                            stack.push(tmp);
                        }
                    } else if (top == '{') {
                        if (tmp == '}') {
                            stack.pop();
                        } else {
                            stack.push(tmp);
                        }
                    } else {
                        return false;
                    }
                }
            }
            return stack.isEmpty();
        }
    }