20. Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

·

4 min read

The function isValid takes a string s as input and checks if it contains a valid set of parentheses, brackets, and curly braces. Here's a step-by-step visualization of how the function works:

  1. Declare an empty array arr to store opening parentheses, brackets, and curly braces.

     const arr = [];
    
  2. Loop through each character in the input string s using a for loop. The loop iterates from the index 0 to the length of the string - 1.

     for(let i = 0; i < s.length; i++){
       // code goes here
     }
    
  3. For each character in the string, check if it's an opening parenthesis, bracket, or curly brace. If it is, add the corresponding closing parentheses, bracket, or curly brace to the arr array using the push method.

     let char = s.charAt(i);
    
     switch(char){
       case '(': arr.push(')')
       break;
       case '{': arr.push('}')
       break;
       case '[': arr.push(']')
       break;
     }
    
  1. If the character is not an opening parenthesis, bracket, or curly brace, it must be closing parentheses, bracket, or curly brace. In that case, pop the last element from the arr array and compare it to the current character. If they don't match, return false because the string is not valid. If they do match, continue the loop.

     default: if(char !== arr.pop()) return false
    
  2. After the loop finishes, check if the arr array is empty. If it is, all opening parentheses, brackets, and curly braces have been matched with their corresponding closing parentheses, brackets, and curly braces. Return true to indicate that the string is valid. If the arr array is not empty, some opening parentheses, brackets, or curly braces have not been matched, so return false.

     return arr.length === 0;
    

Here's the full function code for reference:

var isValid = function(s){
  const arr = [];
  for(let i = 0; i < s.length; i++){
    let char = s.charAt(i);
    switch(char){
      case '(': arr.push(')')
      break;
      case '{': arr.push('}')
      break;
      case '[': arr.push(']')
      break;
      default: if(char !== arr.pop()) return false
    }
  }
  return arr.length === 0;
};

Suppose we call the isValid function with the following input string:

isValid("{{([])}})")
  1. The isValid function initializes an empty array arr to store opening parentheses, brackets, and curly braces.

     const arr = [];
    
  1. The function loops through each character in the input string "{{([])}})".

     for (let i = 0; i < s.length; i++) {
       let char = s.charAt(i);
       // Code to check if `char` is a valid opening or closing parentheses, bracket, or curly brace
     }
    
  1. The first character is {, which is a valid opening curly brace. The function adds the corresponding closing curly brace } to the arr array using the push method.

     switch(char) {
       case '(': arr.push(')');
       break;
       case '{': arr.push('}');
       break;
       case '[': arr.push(']');
       break;
     }
     // After adding `}` to `arr`, `arr` now contains `['}']`.
    
  1. The next character is {, which is another valid opening curly brace. The function adds the corresponding closing curly brace } to the arr array.

     switch(char) {
       case '(': arr.push(')');
       break;
       case '{': arr.push('}');
       break;
       case '[': arr.push(']');
       break;
     }
     // After adding `}` to `arr`, `arr` now contains `['}', '}']`.
    
  1. The next character is [, which is a valid opening bracket. The function adds the corresponding closing bracket ] to the arr array.

     switch(char) {
       case '(': arr.push(')');
       break;
       case '{': arr.push('}');
       break;
       case '[': arr.push(']');
       break;
     }
     // After adding `]` to `arr`, `arr` now contains `['}', '}', ']']`.
    
  1. The next character is (, which is a valid opening parenthesis. The function adds the corresponding closing parentheses ) to the arr array.

     switch(char) {
       case '(': arr.push(')');
       break;
       case '{': arr.push('}');
       break;
       case '[': arr.push(']');
       break;
     }
     // After adding `)` to `arr`, `arr` now contains `['}', '}', ']', ')']`.
    
  1. The next character is ], which is not a valid opening or closing parentheses, bracket, or curly brace. The function pops the last element from the arr array, which is ). Since ] does not match ), the function returns false.

     default: if(char !== arr.pop()) return false;
     // Since `]` does not match `)`, the function returns `false`.
    
  1. The function stops executing and returns false because there is a mismatched closing bracket in the input string "{{([])}})".

Therefore, the function returns false for this input string, indicating that it does not contain a valid set of parentheses, brackets, and curly braces.