leetcode - 20.有效的括号（LinkedHashMap）

leetcode题目有效的括号，分类是easy，但是博主前前后后提交了几十次才通过，现在记录一下使用Java语言的写法。

题目链接: 20.有效的括号

题目描述：

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。有效字符串需满足：
1.左括号必须用相同类型的右括号闭合。
2.左括号必须以正确的顺序闭合。
3.每个右括号都有一个对应的相同类型的左括号。

题目示例：

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

题目提示：

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

题目解读：

每个左括号都要有成对的右括号，成对的含义是
（1）属于"()"、"[]"、"{}"中的任意一对
（2）中间不存在其他字符，比如"()"
（3）中间存在其他成对的字符，比如"({[]})"

示例图：

一、 递归

基于以上的理解，博主最初选择使用递归消除字符的做法。只要左右相邻的字符成对就将其消除，递归至LinkedHashMap的长度为0或不再出现可消除的字符。

思路：
（1）使用LinkedHashMap保存入参用例中的所有字符。
（2）遍历LinkedHashMap，在存在相邻两个元素符合成对匹配条件时，将这两个元素记录下来，在一次遍历结束后从LinkedHashMap中移除。
（3）当LinkedHashMap长度为0，或者在一次遍历中没有产生新的待删除的元素，则跳出循环。
（4）当最终LinkedHashMap长度为0时，说明全部匹配成功。

class Solution {public boolean isValid(String s) {boolean res = false;char[] charArray = s.toCharArray();if (charArray.length % 2==1) {return res;}HashMap<Integer, String> linkedHashMap = new LinkedHashMap<>();for (int i =0; i < charArray.length; i++) {linkedHashMap.put(i, String.valueOf(charArray[i]));}List<String> leftList = Arrays.asList("(", "[", "{");List<String> rightList = Arrays.asList(")", "]", "}");// 当map中全部消除完，或上一轮没有可消除的值时跳出循环int lastIndex = 0;List<Integer> removeKeys = new ArrayList<>();while (!linkedHashMap.isEmpty()) {removeKeys = new ArrayList<>();for (Integer key : linkedHashMap.keySet()) {int pos = new ArrayList<Integer>(linkedHashMap.keySet()).indexOf(key);// 从第二个开始跟前面的比较，前面取最新的linkedMap的第一个，不是key=0if (pos > 0) {if (leftList.contains(linkedHashMap.get(lastIndex))&& rightList.contains(linkedHashMap.get(key))&& (leftList.indexOf(linkedHashMap.get(lastIndex)) == rightList.indexOf(linkedHashMap.get(key)))) {// 删除对应位置removeKeys.add(lastIndex);removeKeys.add(key);linkedHashMap.put(lastIndex, "0");linkedHashMap.put(key, "0");}}// 保存上一个key的值lastIndex = key;}if (!removeKeys.isEmpty()) {removeKeys.forEach(linkedHashMap::remove);} else {break;}}if (linkedHashMap.isEmpty()) {res = true;}return res;}}

该做法可以计算正确，但在遇到以下测试用例时，惨遭Time Limit Exceeded 👇。

String s = "[([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([()])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])]";

该测试用例长度为7000，以递归消除元素的方法需要递归遍历几千次，速度非常的慢。那么，提高速度最好的办法就是减少遍历次数。

二、栈

在评论区看了一圈，发现大佬们的基本都是用栈来解决。
但是博主平时基本不使用栈这种数据结构，对栈的了解仅停留在以下层面。

栈（Stack）是一种常见的数据结构，具有后进先出（LIFO，Last In First Out）的特性，即最后入栈的元素最先出栈。

所以依然选择使用熟悉的LinkedHashMap去实现LIFO这一行为。在加入LinkedHashMap前先判断是否与末尾的元素匹配，再决定后续的操作。仅需要遍历一次就可以完成所有的匹配判断。

思路：
（1）遍历入参的字符数组。
（2）如果linkedMap长度为空，当前字符直接加入，作为第一个字符。
（3）如果linkedMap长度不为空，取末尾元素与当前元素进行匹配。匹配成功，将末尾元素消除（弹出）；匹配失败，将当前元素加入linkedMap（压入）
（4）字符数组遍历结束后，如果linkedMap为空，说明全部匹配。

class Solution {public boolean isValid(String s) {boolean res = false;char[] charArray = s.toCharArray();if (charArray.length % 2==1) {return res;}List<String> leftList = Arrays.asList("(", "[", "{");List<String> rightList = Arrays.asList(")", "]", "}");// 栈：一个一个往堆栈里填入，如果跟前一个匹配就双双丢出HashMap<Integer, String> linkedHashMap = new LinkedHashMap<>();for (int i =0; i < charArray.length; i++) {String s1 = String.valueOf(charArray[i]);// 当前linkedMap中的排列的第一位if (i== 0 || linkedHashMap.isEmpty()) {if (rightList.contains(s1)) {return false;}linkedHashMap.put(i, String.valueOf(charArray[i]));} else {int lastPos = new ArrayList<Integer>(linkedHashMap.keySet()).get(linkedHashMap.size()-1);// 判断跟linkedMap中最新一位元素是否匹配String lastS1 = linkedHashMap.get(lastPos);if (leftList.contains(lastS1)&& rightList.contains(s1)&& (leftList.indexOf(lastS1) == rightList.indexOf(s1))) {// 匹配成功，不加入linkedMap，并且将前一个元素从map中移除（弹出）linkedHashMap.remove(lastPos);} else {// 不匹配，将该元素加入linkedMap中（压入）linkedHashMap.put(i, String.valueOf(charArray[i]));}}}// 全部消除完毕才是通过if (linkedHashMap.isEmpty()) {res = true;}return res;}
}

不过在使用LinkedHashMap时也碰到了一些问题，因为元素可以随意移除，所以key的排序不是连续的12345等。需要将key转为ArrayList，再通过ArrayList.get()方法获取最新一位元素key。