Valid Parenthesis

Short Summary

Given a string containing parenthesis characters, evaluate if the parenthesis formation are valid.

---

I/O Example

// inputStr := "()[]{}"
// output := myFunction(inputStr)
// output = true

// inputStr2 := "()[]{[)]}"
// output2 := myFunction(inputStr2)
// output2 = false

---

Explanation and Walk-through

First, let's review the parenthesis validation rules.

• Every opening parenthesis needs a closer in the correct order to be valid.
• If there are nested pairs, they need to be closed in the reverse order they are opened.

From the second rule, we can infer that we need to keep track of the characters in a LIFO order. So the last opened parenthesis must be closed the first. Which implies a stack data structure. With a stack we can naturally keep track of a LIFO order operation. So let's jump into the code.

Our algorithm will go through all the characters (runes in golang) of the string and do the following operation:

• If it's an opener, push it to the stack
• If it's a closer, pop from the stack and see if they match. (Last opened needs to be closed first)
  • if they match, continue, we still have a valid sequence.
  • if they don't match or the stack is empty (so no pop) then return false immediately.
• Once every character of the string is processed, check if there's anything left in the stack. If there's anything left, that would mean there are unmatched openers in the string, so return false. Otherwise our string is valid.

For the code below to work, you need to implement the stack (runeStack in this case) and the matches function. Matches function accepts two runes as parameters and checks if the second rune is the correct closer for the first one.

func isValid(s string) bool {
	// for every rune
	// if it's an opener
	// push it to the stack
	// if it's a closer, pop from the stack and compare current to popped to see if it matches.
	// if no match, return false
	// if stack is empty and string has no more runes return true
	stack := runeStack{}

	for _, r := range []rune(s) {
		switch r {
		case '{', '[', '(':
			stack.push(r)
		case '}', ']', ')':
			if stack.isEmpty() {
				return false
			} else {
				cur := stack.pop()
				if !matches(cur, r) {
					return false
				}
			}
		}
	}
	return stack.isEmpty()
}

---

For the full code, feel free to reach out.

You can try it yourself on leetcode

---

Please comment or dm me if you have other questions or remarks.

Until next time,

Stay all in!

Reha S.

Oct 07 2022