Introduction
In this article, we will solve leetcode's 20th problem: Valid Parentheses. This is the best example to understand how stack works. In the last article, we implemented stack in JavaScript. In this article, we are going to solve this example in both languages C# and JavaScript.
Here is the problem from leetcode,
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]"
Output: false
Solution
We already know which data structure is best for this problem. Now to figure out the rest of the logic we need to find the pattern in the problem, as you can see parenthesis come in a pair, "{ }", "[ ]", "( )". We can use switch statements to find a matching pair. If we get "{" we will push "}" into the stack, if we get "[" we will push "]", if we get "('' we will push")".
There are 3 possibilities to check failed test cases,
- Having no matching pair : { (
- Having wrong matching pair: { )
- Having only one of the parenthesis: )
public class Solution {
public bool IsValid(string s) {
Stack < char > paranthesisStack = new();
foreach(char item in s) {
switch (item) {
case '{':
paranthesisStack.Push('}');
break;
case '[':
paranthesisStack.Push(']');
break;
case '(':
paranthesisStack.Push(')');
break;
case '}':
case ']':
case ')':
if (paranthesisStack.Count == 0) return false;
if (paranthesisStack.Pop() != item) return false;
break;
default:
break;
}
}
return paranthesisStack.Count == 0;
}
}
Listing 1: Valid parenthis
Test case 1: "{ ( [ ] ) }" //working test case.
Iteration 1:
Current char: {
Stack.push: }
Stack: }
Stack.Length = 1
Iteration 2:
Current char: (
Stack.push: )
Stack: ) -> }
Stack.Length = 2
Iteration 3:
Current char: [
Stack.push: ]
Stack: ] -> ) -> }
Stack.Length = 3
Iteration 4:
Current char: ]
Stack.Pop: ]
Stack: ) -> }
Stack.Length = 2
Iteration 5:
Current char: )
Stack.push: )
Stack: }
Stack.Length = 1
Iteration 6:
Current char: }
Stack.push: }
Stack: empty
Stack.Length = 0
Test Case 2: "{)" //failed test case, having wrong matching pair
Iteration 1:
Current char: {
Stack.push: }
Stack: }
Stack.Length = 1
Iteration 2:
Current char: )
Stack.Pop: }
Stack.Length = 1
Check if removing item is the same
) != }
return false
Test case 3: "{ (" //failed test case, having no matching pair
Iteration 1:
Current char: {
Stack.push: }
Stack: }
Stack.Length = 1
Iteration 2:
Current char: (
Stack.push: )
Stack: ) -> }
Stack.Length = 2
Come out of switch,
Check if length is not 0.
return false
Test case 4: ")" //failed test case, having only one of the parenthesis
Iteration 1:
Current char: )
Stack.Pop: )
Stack.Length = 1
Inside switch: check if length is 0.
return false
Let's implement the same logic in JavaScript. JavaScript doesn't have an inbuilt stack, we have created a stack in the last article, you can find it here.
Note
This problem can be solved with arrays too, our goal here is to understand how stack works. That's why we have created a stack in JS and we are going to use class stack to solve this problem.
Note2
We are not returning an item to be deleted in pop, so we just need to add one more else to our condition.
function isValid(s) {
var paranthesisStack = new Stack();
for (let i = 0; i < s.length; i++) {
switch (s[i]) {
case '{':
paranthesisStack.push('}');
break;
case '[':
paranthesisStack.push(']');
break;
case '(':
paranthesisStack.push(')');
break;
case '}':
case ']':
case ')':
if (paranthesisStack.isEmpty()) return false;
if (paranthesisStack.peek().value !== s[i]) {
return false;
} else {
paranthesisStack.pop();
}
break;
default:
break;
}
}
return paranthesisStack.isEmpty();
}
Listing 2: isValid method in JavaScript
Just to give you a glance of class stack, here is source code for class Node and Stack.
class Node {
constructor(value) {
this.value = value,
this.next = null
}
}
class Stack {
constructor() {
this.top = null,
this.bottom = null,
this.length = 0
}
push(value) {
var newTopNode = new Node(value);
if (this.length === 0) {
this.top = newTopNode;
this.bottom = newTopNode;
} else {
const tempNode = this.top;
this.top = newTopNode;
this.top.next = tempNode;
}
this.length++;
return this;
}
pop() {
if (!this.top) {
return null;
}
if (this.top === this.bottom) {
this.bottom = null;
}
this.top = this.top.next;
this.length--;
return this;
}
peek() {
return this.top;
}
isEmpty() {
return this.length === 0;
}
size() {
return this.length;
}
printList() {
//Creates an empty array.
let printArrayList = [];
//Pointer which points to the head node
let currentNode = this.top;
//Start iterating from the first node till you reach the last node
while (currentNode !== null) {
//Add every node's value to the array
printArrayList.push(currentNode.value);
//Point pointer to the next node
currentNode = currentNode.next;
}
//Return the array
return printArrayList.join(' -> ');
}
}
Listing 3: class stack in javascript
Summary
There are thousands of ways to solve the problem, always choose the one with the best time complexity.