算法练习：判断字符串中的括号字符是否对称

题目：给定一个只包含大、中、小括号的字符串，判断字符串是否有效。也就是同一种括号的左右部分需要对应。

例如：

()–合法

[]–合法

[()]–合法

{()}–合法

[(])–不合法

[)]–不合法

实现思路：左括号默认就合法，需要再检查是否有匹配的右括号。
左括号–》压入堆栈右括号–》同栈顶元素进行匹配检查，匹配则栈顶元素pop，不匹配说明该字符串不合法如果能匹配上，堆栈必然是空的。

时间复杂度O(n)

空间复杂度O(n)

代码如下：

package com.example.demo;

import java.util.Stack;

public class ValidString {

    public static void main(String[] args) {
        char[] chars_1 = {'(',')'};//合法
        char[] chars_2 = {'(',')','[',']'};//合法
        char[] chars_3 = {'(',')','[',']','[','}'};//不合法
        System.out.println(valid(chars_1));
        System.out.println(valid(chars_2));
        System.out.println(valid(chars_3));
    }

    public static boolean valid(char[] chars) {
        Stack<Character> stack=new Stack<>();
        for(char c: chars) {
            if(c == '(') {
                stack.push(c);
            } else if(c == '[') {
                stack.push(c);
            } else if(c == '{') {
                stack.push(c);
            } else if(c == ')') {
                if(stack.empty()) {
                    return false;
                }
                Character peek = stack.peek();
                if(peek == '(') {
                    stack.pop();
                } else {
                    return false;
                }
            } else if(c == ']') {
                if(stack.empty()) {
                    return false;
                }
                Character peek = stack.peek();
                if(peek == '[') {
                    stack.pop();
                } else {
                    return false;
                }
            } else if(c == '}') {
                if(stack.empty()) {
                    return false;
                }
                Character peek = stack.peek();
                if(peek == '{') {
                    stack.pop();
                } else {
                    return false;
                }
            }

        }
        if(!stack.empty()) {
            return false;
        }
        return true;
    }

}

结果：

true
true
false

上面的代码看起来比较冗余，不够简洁，还有一种思路，能够让代码简洁。思路就是将括号放入map，根据每次的括号，来判断是左括号就压入栈，右括号就判断与前一个字符是否对称。

代码如下：

package com.example.demo;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class ValidString2 {

    public static void main(String[] args) {
        char[] chars_1 = {'(',')'};//合法
        char[] chars_2 = {'(',')','[',']'};//合法
        char[] chars_3 = {'(',')','[',']','[','}'};//不合法
        System.out.println(valid(chars_1));
        System.out.println(valid(chars_2));
        System.out.println(valid(chars_3));
    }

    public static boolean valid(char[] chars) {
        Map<Character,Character> mapChar = new HashMap<>();
        mapChar.put(')','(');
        mapChar.put(']','[');
        mapChar.put('}','{');

        Stack<Character> stack=new Stack<>();
        for(char c :chars) {
            if(!mapChar.containsKey(c)) {
                //不在map的key中说明是左括号，要放入stack中
                stack.push(c);
            } else {
                //在map的key中，说明是右括号，要判断是否合法
                if(stack.empty()) {
                    return false;
                }
                Character peek = stack.peek();
                if(peek == mapChar.get(c)) {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        if(!stack.empty()) {
            return false;
        }
        return true;
    }
}

结果：

true
true
false

第二种实现比第一种实现的valid方法，精简了很多，思路也并不复杂。