[算法] [leetcode-20] 有效的括号

20 有效的括号

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = “()”

输出：true

示例 2：

输入：s = “()[]{}”

输出：true

示例 3：

输入：s = “(]”

输出：false

示例 4：

输入：s = “([])”

输出：true

 class Solution {
        public boolean isValid(String s) {
            if(null ==  s) {
                return true;
            }
            char[] charArray = s.toCharArray();
            Stack<Character> characterStack = new Stack<>();
            for (char charSingle : charArray) {
                characterStack.push(charSingle);
            }
            Set<Character> leftCharacterSet = new HashSet<Character>();
            leftCharacterSet.add('(');
            leftCharacterSet.add('[');
            leftCharacterSet.add('{');
            Set<Character> specialCharacterSet = new HashSet<Character>();
            specialCharacterSet.add('(');
            specialCharacterSet.add('[');
            specialCharacterSet.add('{');
            specialCharacterSet.add('}');
            specialCharacterSet.add(']');
            specialCharacterSet.add(')');

            boolean flag = true;
            while(!characterStack.isEmpty()){
                Character leftCharacter = null;
                Character tmpArray[] = new Character[s.length()];
                int index = 0;
                while (!characterStack.isEmpty()){
                    Character tmpChar = characterStack.pop();
                    if(leftCharacterSet.contains(tmpChar)){
                        leftCharacter = tmpChar;
                        break;
                    }
                    tmpArray[index++] = tmpChar;
                }
                if(leftCharacter == null) {
                    for(int i=index-1; i>=0 ;i--){
                        if(specialCharacterSet.contains(tmpArray[i])){
                            flag = false;
                            break;
                        }
                    }
                    if(!flag){
                        break;
                    }
                }
                if(index == 0) {
                    flag = false;
                    break;
                }
                Character matchCharacter = findMatchCharacter(leftCharacter);
                for(int i=index-1; i>=0 ;i--){
                    if(matchCharacter.equals(tmpArray[i])){
                        // 匹配后重新塞入
                        for(int j=i-1; j>=0; j--){
                            characterStack.push(tmpArray[j]);
                        }
                        break;
                    } else if(specialCharacterSet.contains(tmpArray[i]) && !matchCharacter.equals(tmpArray[i])){
                        flag = false;
                        break;
                    }
                }
                if(!flag){
                    break;
                }
            }
            return flag;
        }

        public Character findMatchCharacter(Character leftChar) {
            if (leftChar.equals('(')) {
                return ')';
            }
            if (leftChar.equals('[')) {
                return ']';
            }
            if (leftChar.equals('{')) {
                return '}';
            }
            return '|';
        }
    }