I. Title Description:
The original address
Given a only include a ‘(‘,’) ‘, ‘{‘,’} ‘, ‘/’, ‘ ‘the string s, determine whether a string is effective.
A valid string must meet the following requirements:
An open parenthesis must be closed with a close parenthesis of the same type. The left parentheses must be closed in the correct order.
Tip:
- 1 <= s.length <= 10^4
- S consists only of parentheses ‘()[]{}’
Example 1: Input: s = "()" Output: trueCopy the code
Example 2: Input: s = "()[]{}" Output: trueCopy the code
Example 3: Input: s = "(]" Output: falseCopy the code
Example 4: Input: s = "([)]" Output: falseCopy the code
Example 5: Input: s = "{[]}" Output: trueCopy the code
Ii. Analysis of Ideas:
In fact, the typical stack thinking.
- It’s only parentheses, so it’s only STR that has an odd length is definitely not valid
- Traversal string
- When it hits an open parenthesis, it pushes it into another array
- If I see a close bracket, I’m going to see if it’s the last item in the array and if I see a close bracket, I’m going to throw the last item out of the array
- If there is a string in the array, it is invalid. If there is a string in the array, it is invalid
A slightly more subtle twist of js: the map type maps open parentheses to close parentheses
Iii. AC Code:
/ * * *@param {string}
* @return {boolean}* /
const isValid = function (s) {
if (s.length % 2= = =1) {
return false;
}
const res = [];
const map = new Map([['['.'] '],
['('.') '],
['{'.'} ']]);for (const str of s) {
const isLeft = map.has(str);
if(isLeft || ! res.length) res.push(str);else {
// if it is the right symbol, see if it is the right parenthesis corresponding to the last open parenthesis of the res
If yes, delete the last one; if no, return false
if (map.get(res[res.length - 1]) !== str) {
return false; } res.pop(); }}return! res.length; };Copy the code
Iv. Summary:
- The application of stack idea
- Use of map types