一、问题

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

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

注意：空字符串可被认为是有效字符串。

示例 1：
输入："()"
输出：true

示例 2：
输入："()[]{}"
输出：true

示例 3：
输入："(]"
输出：false

示例 4：
输入："([)]"
输出：false

示例 5：
输入："{[]}"
输出：true

二、理解

验证括号的对称性，括号总共分为三类：小括号、中括号和大括号，可以利用栈先进后出的特性，将所有左括号【“(”、“[”、“{”】先入栈，然后再碰到右括号时，让它与栈顶的元素进行匹配，比如当遇到“)”时，如果栈顶是“(”，则说明匹配成功，栈顶元素出栈再继续字符串循环的流程，如果匹配错误就直接返回 false。假设要匹配字符串“(([]))”是否合法，执行流程如下：

首先遇到左括号，先入栈： 接下来又是左括号，继续入栈： 然后又是左括号，继续入栈： 接下来是右括号，与栈顶元素匹配，“[]”为一对合法的括号，匹配成功栈顶元素出栈： 接下来又是右括号，与栈顶元素匹配，“()”为一对合法的括号，匹配成功栈顶元素出栈： 接下来又是右括号，与栈顶元素匹配，“()”为一对合法的括号，匹配成功栈顶元素出栈： 当字符串循环结束并且栈为空栈时，则证明此字符串的括号匹配合法，最终的效果如下图所示：

三、解答

测试主类：

public static void main(String[] args) {
    String s = "()";
    Test test = new Test();
    System.out.println(test.isValid(s));
}

1️⃣判断括号的有效性可以使用栈这一数据结构来解决。

遍历给定的字符串 ss，当遇到一个左括号时，期望在后续的遍历中，有一个相同类型的右括号将其闭合。由于后遇到的左括号要先闭合，因此可以将这个左括号放入栈顶。

当遇到一个右括号时，需要将一个相同类型的左括号闭合。此时，可以取出栈顶的左括号并判断它们是否是相同类型的括号。如果不是相同的类型，或者栈中并没有左括号，那么字符串 ss 无效，返回 false。为了快速判断括号的类型，可以使用哈希映射(HashMap)存储每一种括号。哈希映射的键为右括号，值为相同类型的左括号。

在遍历结束后，如果栈中没有左括号，说明字符串 ss 中的所有左括号完成闭合，返回 true，否则返回 false。

注意到有效字符串的长度一定为偶数，因此如果字符串的长度为奇数，可以直接返回 false，省去后续的遍历判断过程。

public boolean isValid(String s) {
    int n = s.length();//括号的长度
    if (n % 2 == 1) {//括号不是成对的直接返回 false
        return false;
    }
    //把所有对比的括号存入 map，对比时用
    Map<Character, Character> pairs = new HashMap<Character, Character>() {{
        put(')', '(');
        put(']', '[');
        put('}', '{');
    }};
    //定义栈，用于存取括号（辅助比较）
    Deque<Character> stack = new LinkedList<Character>();
    //循环所有字符
    for (int i = 0; i < n; i++) {
        char ch = s.charAt(i);
        //为右边的括号，如 ')'、'}' 等
        if (pairs.containsKey(ch)) {
        //栈为空或括号不匹配
            if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
                return false;
            }
            //是一对括号，执行出栈（消除左右括号
            stack.pop();
        } else {
            //左边括号，直接入栈
            stack.push(ch);
        }
    }
    return stack.isEmpty();
}

2️⃣解题思路：

1. 特判：过滤空字符串。
2. 创建一个辅助栈。
3. 遍历，对每一个字符进行如下操作：
   ①若为左括号，则往栈中存放右括号。
   ②若为右括号，如果栈为空或者该右括号与取出的栈顶元素不一样，则返回 false。
4. 返回栈是否为空的状态。

public boolean isValid(String s) {
    //1.特判
    if (s.isEmpty()) return true;
    //2.创建辅助栈
    Stack<Character> stack = new Stack<>();
    //3.遍历
    for (char c : s.toCharArray()) {
        if (c == '(') {
            stack.push(')');
        } else if (c == '[') {
            stack.push(']');
        } else if (c == '{') {
            stack.push('}');
        } else if (stack.isEmpty() || c != stack.pop()) {
            return false;
        }
    }
    //4.返回
    return stack.isEmpty();
}

3️⃣可以使用借助 Java 中的 replace 方法来实现，循环的消除字符串中的括号，比如将“()”或“[]”或“{}”循环得替换为空，最后在执行完成之后如果字符串为空，则说明字符串中的括号是合法的，具体实现代码如下：

public boolean isValid(String s) {
   int len;
   do {
       len = s.length();
       //消除成双成对的符号
       s = s.replace("()", "").replace("[]", "").
               replace("{}", "");
    } while (len != s.length()); //不能再进行替换了，replace没有替换任何字符
    return s.length() == 0;
}