theme

Given a string containing only ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘, ‘]’, check whether the string is valid. 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.
  • Note that an empty string can be considered a valid string.

The sample

Example 1:

  • Input: “()”
  • Output: true,

Example 2:

  • Input: “[] {} ()”
  • Output: true,

Example 3:

  • Input: “[]”
  • Output: false

Example 4:

  • Input: “(())”
  • Output: false

Example 5:

  • Input: {} [] “”
  • Output: true,

Their thinking

  1. Check if the string length is even. If it is not, return false
  2. A hash Map b hash Map C hash Map D hash Map
  3. The analysis shows that: the left parenthesis encountered is pushed to the top of the stack, and the left parenthesis encountered in the stack is popped out for matching. False If the match is successful, the system goes to the next round
  4. Check whether the heap is empty or not until the whole string is compared: false: true

The problem solving source

  • The source code for the first time
/ * * *@param {string} s
 * @return {boolean}* /
/* Open parenthesis single */ open parenthesis single */
var isValid = function (s) {
    // create a linear table that mimics the stack
       // Take the beginning of the string to determine: open parenthesis or close parenthesis
          // 1. Open parenthesis: Keep looking until you find the innermost open parenthesis and push the open parenthesis to the top of the stack
          // Find the first close parenthesis and pop the innermost open parenthesis to see if it matches
               // Does not match false
               / / match is true
                   // If the string has close parentheses, there are no open parentheses in the stack -> close parentheses single false
                   // If the stack has an open parenthesis, there is no -> open parenthesis in the string false
          // 2. Close parenthesis: false
    If the length is odd, return false */
    length = s.length;
    if(length % 2! =0) {/ / optimization
        return false;
    }

    // hash mapping
    // Declare a map collection
    var myMap = new Map([[') '.'('],
        ['} '.'{'],
        ['] '.'[']]);// Define a stack: a stack is equivalent to a special linked list
    var stk = [];

    var rightKH = s.charAt(0);
    // We can use the charAt() function for strings to get the current value
    for(var i = 0; i < length; i++){
        rightKH = s.charAt(i);
        // If the parenthesis is left, keep looking
        if(rightKH == "(" || rightKH == "{" || rightKH == "[") {// Put the left parenthesis on the stack
            stk.push(rightKH);
        }else {
            var value = stk.pop();
            // The current close parenthesis checks if there is a matching open parenthesis
            if(rightKH == ")") {if(myMap.get(")") != value){
                    return false; }}else if(rightKH == "}") {if(myMap.get("}") != value){
                    return false; }}else if(rightKH == "]") {if(myMap.get("]") != value){
                    return false; }}}}if(stk.length ! =0) {return false;
    }
    return true;
};
/* Add a variable in js: Const let var 1. Variables defined by const cannot be modified and must be initialized. 2. No error */
Copy the code
  • Second source code
var isValid = function (s) {
    length = s.length;
    if(length % 2! =0) {return false;
    }

    // hash mapping
    // Declare a map collection
    var myMap = new Map([[') '.'('],
        ['} '.'{'],
        ['] '.'[']]);// Define a stack: a stack is equivalent to a special linked list
    var stk = [];

    var rightKH = s.charAt(0);
    // We can use the charAt() function for strings to get the current value
    for(var i = 0; i < length; i++){
        rightKH = s.charAt(i);
        // If the parenthesis is left, keep looking
        if(rightKH == "(" || rightKH == "{" || rightKH == "[") {// Put the left parenthesis on the stack
            stk.push(rightKH);
        }else {
            var value = stk.pop();
            // The current close parenthesis checks if there is a matching open parenthesis
            // if(rightKH == ")"){
            // if(myMap.get(")") ! = value){
            // return false;
            / /}
            // }else if(rightKH == "}"){
            // if(myMap.get("}") ! = value){
            // return false;
            / /}
            // }else if(rightKH == "]"){
            // if(myMap.get("]") ! = value){
            // return false;
            / /}
            // }
            // Replace the above with the following statement
            if(myMap.get(rightKH) ! = value){// console.log(myMap.get(rightKH));
                return false; }}}if(stk.length ! =0) {return false;
    }
    return true;
};
Copy the code
  • Operation efficiency

Pay attention to

Const let var = const let var

  • Variables defined by const cannot be modified and must be initialized
  • The variable block-level scope defined by let has no effect on the outside of the function after the let definition is used inside the function
  • The variable defined by var can be modified. If it is not initialized, undefined will be output without error

Code optimization

// Two matching problems, then the string length must be even
  if(length % 2! =0) {/ / optimization
        return false;
    }
Copy the code

Code error point

// Check whether the stack is empty
if(stk.length ! =0) {return false;
}
   return true;
Copy the code

Study the Map

  • A declarative way
var myMap = new Map([[') '.'('],
      ['} '.'{'],
      ['] '.'[']]);Copy the code
  • Obtain the corresponding value by key
myMap.get(rightKH) -> value
Copy the code