Valid Parentheses w/o Stack

Let’s start from where left off —

Oh, wait. For those who are wondering where I left off in the first place, you might want to take a look at this.

Goal: Try to reduce the memory usage and make the implementation faster than Approach 1

//Approach 2
//Using Linked Lists
//Time taken - 3ms
//Memory usage - 37.1MB
//Deliberately avoided using Maps
private class OpeningBracket{
  char type;
  OpeningBracket previousOpeningBracket;
 }
 
 public boolean isValid(String s) {
  char[] brackets = s.toCharArray();
  OpeningBracket previousOpeningBracket = null;
  
  for(char bracket : brackets) {
   switch(bracket) {
   case '(':
   case '{':
   case '[':
    OpeningBracket currentOpeningBracket = new OpeningBracket();
    currentOpeningBracket.type = bracket;
    currentOpeningBracket.previousOpeningBracket = previousOpeningBracket;
    previousOpeningBracket = currentOpeningBracket;
    break;
   case ')':
    if(previousOpeningBracket!=null && previousOpeningBracket.type=='(') {
     previousOpeningBracket = previousOpeningBracket.previousOpeningBracket;
    } else {
     return false;
    }
    break;
   case '}':
    if(previousOpeningBracket!=null && previousOpeningBracket.type=='{') {
     previousOpeningBracket = previousOpeningBracket.previousOpeningBracket;
    } else {
     return false;
    }
    break;
   case ']':
    if(previousOpeningBracket!=null && previousOpeningBracket.type=='[') {
     previousOpeningBracket = previousOpeningBracket.previousOpeningBracket;
    } else {
     return false;
    }
    break;
   }
  }
  return null==previousOpeningBracket;
 }
/*************************************************************/
//Approach 3
//Borrowed the LinkedList concept
//But used just the indices
//Time taken: 2ms
//Memory usage: 37.3MB (Well that remains terrible)
public boolean isValid(String s) {
  char[] brackets = s.toCharArray();
  int length = brackets.length;
  int[] previousIndices = new int[length];
  int previousOpeningBracketIndex = -1;
  char bracket;
  for(int index =0;index<length; index++) {
   bracket = brackets[index];
   switch(bracket) {
   case '(':
   case '{':
   case '[':
    previousIndices[index] = previousOpeningBracketIndex;
    previousOpeningBracketIndex = index;
    break;
   case ')':
    if(previousOpeningBracketIndex>-1 && brackets[previousOpeningBracketIndex]=='(') {
     previousOpeningBracketIndex = previousIndices[previousOpeningBracketIndex];
    } else {
     return false;
    }
    break;
   case '}':
    if(previousOpeningBracketIndex>-1 && brackets[previousOpeningBracketIndex]=='{') {
     previousOpeningBracketIndex = previousIndices[previousOpeningBracketIndex];
    } else {
     return false;
    }
    break;
   case ']':
    if(previousOpeningBracketIndex>-1 && brackets[previousOpeningBracketIndex]=='[') {
     previousOpeningBracketIndex = previousIndices[previousOpeningBracketIndex];
    } else {
     return false;
    }
    break;
   }
  }
  return previousOpeningBracketIndex==-1;
 }
/*************************************************************/
//Approach 3.1
//Being picky with variable usage
//Eliminating the length variable and 
//Directly using the length property of an Array
//(NOTE: _.length Vs _.size())
//can preserve the speed and reduce memory usage
//Time taken: 2ms
//Memory usage: 36.9MB
public boolean isValid(String s) {
 char[] brackets = s.toCharArray();
 int[] previousIndices = new int[brackets.length];
 int previousOpeningBracketIndex = -1;
 char bracket;
 for(int index =0;index<brackets.length; index++) {
  bracket = brackets[index];
  switch(bracket) {
  case '(':
  case '{':
  case '[':
   previousIndices[index] = previousOpeningBracketIndex;
   previousOpeningBracketIndex = index;
   break;
  case ')':
   if(previousOpeningBracketIndex>-1 && brackets[previousOpeningBracketIndex]=='(') {
    previousOpeningBracketIndex = previousIndices[previousOpeningBracketIndex];
   } else {
    return false;
   }
   break;
  case '}':
   if(previousOpeningBracketIndex>-1 && brackets[previousOpeningBracketIndex]=='{') {
    previousOpeningBracketIndex = previousIndices[previousOpeningBracketIndex];
   } else {
    return false;
   }
   break;
  case ']':
   if(previousOpeningBracketIndex>-1 && brackets[previousOpeningBracketIndex]=='[') {
    previousOpeningBracketIndex = previousIndices[previousOpeningBracketIndex];
   } else {
    return false;
   }
   break;
  }
 }
 return previousOpeningBracketIndex==-1;
}

Summary: Although the implementation may seem superficially different, each of these approaches (including the one that uses the Stack) adopts the same core logic / empirical formula, which is — 1. the newly encountered closing bracket should match the currently active (most recently encountered and unused) opening bracket. 2. And the last check of course, is to ensure that you have exhausted/checked all the brackets.

Find more posts here.

Cheers & Chao!