vaildParentheses.md

Requirements

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

• input: string, made up of '(', ')', '{', '}', '[', and ']'
• output: boolean, if valid parentheses
• constraints:
• edge case: empty string

Strategy

• Use a stack!
• Loop through the string
  • Whenever we encounter an opening character, add it to the stack
  • Whenever we encounter a closing character, pop off the current element at the end of the stack and check if it's the proper opening character, if not return false
• Check if there's anything left in side the stack, if so, return false
• return true

Justification of strategy

We're trying to match together opening and closing pairs, we know that whenever a closing element is encountered that the last opening element encountered should be a match, thus this makes a stack ideal as a way to save opening elements and compare them with closing elements.

Define test cases

'}' => false

'{' => false

'{([])}' => true

'{{{{{}}[[]]}}()}[]' => true

'{{}[]' => false

'(){}]' => false

'' => true

Implementation skeleton

• set stack
• loop through string
  • if character is '(', '{', or '[', add to stack
  • if character is ')', pop from stack, return false if popped is not '('
  • if character is '}', pop from stack, return false if popped is not '{'
  • if character is ']', pop from stack, return false if popped is not '['
• if items still in stack return false
• return true

Actual implementation

https://repl.it/@pmillssf/validParentheses

Execute test cases

run https://repl.it/@pmillssf/validParentheses

Big-O Analysis

Time: O(n)

Space: O(n)

Optimization (if applicable)