leetcode刷题n18-q20：有效的括号

这是我参与11月更文挑战的第21天，活动详情查看：2021最后一次更文挑战

题目描述

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
 

示例 1：

输入：s = "()"
输出：true
示例 2：

输入：s = "()[]{}"
输出：true
示例 3：

输入：s = "(]"
输出：false
示例 4：

输入：s = "([)]"
输出：false
示例 5：

输入：s = "{[]}"
输出：true
 

提示：

1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
复制代码

思路 & CODE

1. 栈

一般括号的题目都是用栈来求解

• 字符串转化为字符数组
• 如果栈空，直接把元素压入栈中
• 如果栈不为空，比较当前元素与栈顶元素是否匹配
  • 如果匹配，栈顶元素出栈，进行下次循环
  • 如果不匹配，当前元素入栈，进行下次循环
• 最后如果栈空返回true，栈不为空返回false

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    for (Character c : s.toCharArray()) {
        if (stack.isEmpty()) {
            stack.push(c);
            continue;
        }
        if (stack.peek() == '(' && c == ')') {
            stack.pop();
        } else if (stack.peek() == '[' && c == ']') {
            stack.pop();
        } else if (stack.peek() == '{' && c == '}') {
            stack.pop();
        }
    }
    return stack.isEmpty();
}
复制代码

2. 字符替换

既然是寻找成对的字符，那么使用while循环，每次替换这些成对的字符为空字符串：

• 定义一个变量用来判断某一次while循环是否发生替换
• 如果替换了就进行下次循环
• 如果没有替换while循环直接结束
• 如果此时字符长度为0说明全都是有效括号，否则说明存在无效括号

public boolean isValid2(String s) {
    boolean hasValid = true;
    while (hasValid) {
        hasValid = false;
        if (s.indexOf("()") != -1) {
            s = s.replace("()", "");
            hasValid = true;
        }
        if (s.indexOf("[]") != -1) {
            s = s.replace("[]", "");
            hasValid = true;
        }
        if (s.indexOf("{}") != -1) {
            s = s.replace("{}", "");
            hasValid = true;
        }
    }
    return s.length() == 0;
}
复制代码