力扣题库20
-
-
-
- 题目介绍
- 思路解析（剥洋葱法）
- 完整代码
- 提交结果
- 思路二（拼对法，也叫栈方法）
- 栈方法提交结果
- 说明
-
-
题目介绍
思路解析（剥洋葱法）
本题用了两种方法解决。 当前介绍第一种： 剥洋葱法。
1， 很明确的是， 左右括号要成对存在。 所以，s.length必须是偶数。 如果是奇数，必定是无效的。
2，依据示例，我们很容易看出，必定有一种括号是紧挨着成对存在的。 比如() [] {}这种形式。
所以，我们就把这些括号一层一层的剥离掉。 直到无法剥离位置。
3，举个例子。 假定s = '{[()]}' 。
4，第一步，检查s中，有没有上述的紧挨着的成对的括号。 可以发现，例子中的s，有一对()是紧挨着的。 我们就把这对紧挨着的括号用''空字符替换（就是所谓的剥离）。
5，此时，s就变成了{[]}， 然后继续检查是否有紧挨着的成对的括号。所以，这一步可以把[]替换成空字符''。
6，到这里，s就只剩下了{}，按照上面的做法，继续剥离。
7，最后，s就变成了''。 此时可以发现，s中所有的括号都是成对存在的，最终被剥离成空字符串。所以，可以判定s是有效的。
否则，s就是无效的。
完整代码
/*** @param {string} s* @return {boolean}*/
var isValid = function(s) {// 奇数个字符 必定无效if(s.length % 2 === 1) {return false;}// 替换函数递归var result = '';function replaceStr(str) {var str1 = str.replace(/\(\)/g, '').replace(/\[\]/g, '').replace(/\{\}/g, '');if(str1 === str) {result = str1;} else {replaceStr(str1);}}replaceStr(s);if(result.length === 0) {return true;} else {return false;}
};
提交结果
思路二（拼对法，也叫栈方法）
1，把括号按照右键左值的形式，保存起来。后续做对比时用。
比如
new Map([[')', '('],[']', '['],['}', '{']])
2，准备一个空数组， 用于保存遍历s的值。
3，对s进行遍历。如果遍历到左括号，就存放到数组里。如果遍历到的是右括号，且能够和存储的左括号拼成一对，就从数组里把对应的括号删掉。
4，一直遍历，存储，删除。如果括号都能拼成对，说明s有效。 否则无效。
该方法比剥洋葱法更快。
栈方法提交结果
可以看出，该思路可以节省至少四分之一的时间。
说明
其他编程语言和方法中，有快到只用2ms 甚至更短时间的。 非常厉害。 可以前往查看。