[算法] [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 '|';}}