代码随想录算法训练营第十一天 | 20. 有效的括号、1047. 删除字符串中的所有相邻重复项

20. 有效的括号

leetcode
文档题解
视频题解

思路：遍历字符串，是左括号就入栈，是右括号就查看栈顶元素（注意栈为空的情况）是否匹配，匹配的话，栈顶元素出栈，否则就不合法。

class Solution {
    public boolean isValid(String s) {
        char[] arr = s.toCharArray();
        Stack<Character> stack = new Stack<>();

        for (char c : arr) {
            if (c == '(' || c == '[' || c == '{') {
                // 左括号，入栈
                stack.push(c);
            } else if (c == ')' || c == ']' || c == '}') {
                // 右括号，拿栈顶元素做匹配
                if (!stack.isEmpty()) {
                    char top = stack.peek();
                    // 不匹配，直接不合法
                    if (c == ')' && top != '(') return false;
                    if (c == ']' && top != '[') return false;
                    if (c == '}' && top != '{') return false;
                    // 匹配，则弹出栈顶元素，检查下一个字符
                    stack.pop();
                } else {
                    // 栈为空，字符串第一个元素就是右括号，直接不合法
                    return false;
                }
            }
        }

        return stack.isEmpty();
    }
}

1047. 删除字符串中的所有相邻重复项

leetcode
文档题解
视频题解

思路：遍历字符串，如果当前字符和栈顶元素不同，则入栈，否则将栈顶元素弹出，最终栈中剩下的就是答案，只不过需要逆序一下。

class Solution {
    public String removeDuplicates(String s) {
        Stack<Character> stack = new Stack<>();

        for (char c: s.toCharArray()) {
            if (stack.isEmpty()) {
                // 如果栈为空，则直接入栈
                stack.push(c);
            } else {
                // 否则要和栈顶元素比较
                char top = stack.peek();
                if (c == top) {
                    stack.pop();
                } else {
                    stack.push(c);
                }
            }
        }

        // 从栈中取出结果
        char[] tmp = new char[stack.size()];
        int i = 0, j = tmp.length - 1;
        while (!stack.isEmpty()) {
            tmp[i++] = stack.pop();
        }

        // 然后逆序
        i = 0;
        for (; i < j; i++, j--) {
            char t = tmp[i];
            tmp[i] = tmp[j];
            tmp[j] = t;
        }

        return new String(tmp);
    }
}