mod4_tech_challenge_2.md

mod4 Tech Challenge 2

Start by opening this URL and reading through the problem https://github.com/turingschool/challenges/blob/master/well_formed_strings.markdown

Make sure you iterate from simple cases to more complex cases If you get done with the example cases, consider the "edge cases", for example: What about an empty "" input? What about just a close ")"? What about too many closes "())" Are any other characters allowed like "( [ ] )"? Pay careful attention to the JavaScript/Ruby test cases. If you finish early, work on the extension problem as well.

What are your initial thoughts about this problem? (high level design, 2-3 sentences)

The problem seems pretty straight forward, however, I bet the solution will be more complex than it appears. I believe I will need to leverage a stack data structure with conditionals to solve this challenge.

Which data structure(s) do you think you'll use? What pros/cons do you see about using it/them?

I plan to use the stack data structure with conditional statements to solve this code challenge. I learned yesterday that a stack is easy to implement with an array. I can use push and/or pop to easily remove elements from the end of the array. One con to using a stack would be the fact that it's more expensive in memory, however, for a challenge this small, this should not be an issue.

Write out your initial pseudocode: (mid-level design, this should not be real code!)

• create a variable for my stack
• create a template object that includes keys of the opening symbol for parenthesis and values that are their closing counterparts
• iterate using a for loop to check if the string coming in has either a (, {, or [, and if so, I will push it into the stack array, otherwise I will pop from the stack array
• if the last element left in the array after all iterating is done is odd, I will return false, otherwise, I will return true

What do you think the Big O complexity of your algorithm is? (just for practice)

I believe the Big O complexity for my solution would be O(n) linear because it is doing a simple iteration through the string using a for loop

solution_techChallenge2.js

const validate_string = string => {

  let stack = [];
  let template = 
    {
      '{': '}',
      '[': ']',
      '(': ')'
    }

    for (let i = 0; i < string.length; i++) {
       
      if (string[i] === '(' || 
          string[i] === '{' || 
          string[i] === '['   ) {
          stack.push(string[i]);
         
        } else {
           
        let stackEnd = stack.pop();
           
        if (string[i] !== template[stackEnd]) {
          return false;
          }
        }
      }
   
    if (stack.length) {
      return false;
    } else {
      return true;
    }
}