Skip to content

Instantly share code, notes, and snippets.

@pmillssf
Last active December 6, 2017 07:00
Show Gist options
  • Save pmillssf/a5cc20110011db32a4f2bc91dc1b2134 to your computer and use it in GitHub Desktop.
Save pmillssf/a5cc20110011db32a4f2bc91dc1b2134 to your computer and use it in GitHub Desktop.

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)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment