This series is nothing fancy, just pure Leetcode problem breakdown analysis, not to use a sexy line or a niche solution, but with clear code and simple enough thinking to help you clarify the problem. Let you in the interview no longer afraid of algorithm written test.

13. Valid-parentheses

The label

  • The stack
  • map
  • simple

The title

Leetcode portal

Let’s just open leetCode.

Parenthesis matching problem.

The relevant knowledge

  1. Map and array relationship
let kvArray = [["key1"."value1"], ["key2"."value2"]].// Use the regular Map constructor to convert a two-dimensional array of key-value pairs into a Map object
let myMap = new Map(kvArray);

myMap.get("key1"); // Return "value1"

The array. from function converts a Map object into a two-dimensional Array of key-value pairs
console.log(Array.from(myMap));  // Print the same array as kvArray

// A more concise way to do the same thing as above is to use the expansion operator
console.log([...myMap]);

// Or use array. from on key or value iterators to get an Array containing only keys or values
console.log(Array.from(myMap.keys())); // output ["key1", "key2"]
Copy the code
  1. You can merge Map objects, but keep the keys unique.
let first = new Map([[1.'one'],
  [2.'two'],
  [3.'three']]);let second = new Map([[1.'uno'],
  [2.'dos']]);// When two maps are merged, if there are duplicate keys, the latter overwrites the former.
// The expansion operator essentially converts a Map object into an array.
let merged = new Map([...first, ...second]);

console.log(merged.get(1)); // uno
console.log(merged.get(2)); // dos
console.log(merged.get(3)); // three
Copy the code
  1. Map objects can also be merged with arrays
let first = new Map([[1.'one'],
  [2.'two'],
  [3.'three']]);let second = new Map([[1.'uno'],
  [2.'dos']]);// When a Map object is merged with an array, if there are duplicate keys, the last one overwrites the previous one.
let merged = new Map([...first, ...second, [1.'eins']]);

console.log(merged.get(1)); // eins
console.log(merged.get(2)); // dos
console.log(merged.get(3)); // three
Copy the code

The basic idea

  1. I’m pushing push when I see an open parenthesis,
  2. When a close parenthesis is encountered and the top of the stack is the corresponding open parenthesis, the top element is pushed off the stack.
  3. Finally, see if there are any other elements in the stack, and if it’s empty, it matches.

Match mappings can be represented by maps.

Writing implement

/ * * *@param {string} s
 * @return {boolean}* /
var isValid = function(s) {
  // Establish the mapping between map and stack
  let map = new Map([[') '.'('],
    ['] '.'['],
    ['} '.'{'],
  ]),
  stack = []
  // Start iterating over the string
  for (i = 0; i < s.length; i++) {
    // When the stack element is more than half of the string, it is impossible to match exactly
    if (stack.length > s.length / 2) {
      return false
    }
    // The top element (stack[stack.length-1]) is not a matching element (map.get(s[I]))
    if (stack.length === 0) {
      stack.push(s[i])
    } else if (stack[stack.length - 1] !== map.get(s[i])) {
      stack.push(s[i])
    } else {
      stack.pop()
    }
  }
  // If the stack is empty at the end, all matches are complete
  return stack.length === 0
};
Copy the code

Let’s do one on the third day of the year.

That’s all for today. If you want to work with me, you can add me to my wechat account infinity_9368, and you can chat with me and add my secret code “Tianwang Gedi Hu”. Verify the message please send me Presious tower shock the reiver monster, I see the pass, the code is not on

reference

  • Developer.mozilla.org/zh-CN/docs/…