Algorithm Practice: Reverse Words in a String

The Grind Continues

Another week, another coding challenge! Since I've been prepping for job interviews, I decided to peruse Glassdoor for common yet challenging coding questions. One of the most frequent ones to appear was the classic 'Reverse String', which I found had a couple of variations.

While it's frequently said, the same advice echoed by coders from years past still rings true: practice builds confidence. Even after just a couple of weeks of challenging myself, I can already see improvements in my approach to problem-solving. This problem was listed as a 'medium' difficulty on both sites I solved it on, and it was super encouraging to discover a working answer in less time than some of my previous challenges!

The Problem: Reverse Words in a String

Similar to the last problem I blogged about, the prompt for this challenge is pretty simple: given an input of a string, return the string in reverse. This doesn't mean to just return everything backward, but rather return every word in the string in reverse order:

Input String = "I code because I'm cool"
Output String = "cool I'm because code I"

It should be noted that these strings can contain leading or trailing spaces with multiple spaces between the words. Despite these added spaces, the returned string should only have single spaces separating words with no leading or trailing spaces (basically we return normal sentences, just reversed).

My Initial Solution

After I first read the prompt, I knew I was going to need a way to store each word from the inputted string. I also knew I could use some trusty JavaScript methods to help meet the sentence requirements put in place by the prompt. After about 15-20 minutes of brainstorming, I got a working solution:

function(string) {
   let s = string.trim().split(' ')
   let reverseArray = []
   let i = s.length

   while(i > 0){
      reverseArray.push(s[i-1])
      i--
   }

   return reverseArray.filter(x => x).join(" ")
}

Breaking it down, the first thing I did was use two JavaScript methods: trim() and split(). The trim() method removes the white spaces on both sides of a string, immediately eliminating unnecessary blanks on the input. This method is followed by the split() method, which takes our string and creates and returns an array populated by substrings. I included a space (' ') as a separator, making each word an element in the returned array. It should be noted that if our sentence contains extra spaces between words, then some of those spaces will find their way into the array:

string = "I have many spaces"
s = [ 'I', 'have', '', '', 'many', 'spaces' ]

I also defined two other variables: reverseArray, which is equal to an empty array, and i, which is equal to the length of our s array. Given its obvious name, reverseArray will eventually store our words contained in the s array, just in reverse order. The i variable exists to be used in the condition of the function's loop.

I decided to use a while loop for the purpose of inserting each element from s into the reverseArray. Since i is equal to the length of s, the program can start inserting each element starting with the last and finishing with the first. Whenever an element is pushed into reverseArray, we get the correct index value by subtracting 1. After an element is inserted, we decrease the value of i by 1 until we hit 0 and the loop breaks. We now have an array with our elements in the required order:

reverseArray = [ 'spaces', 'many', '', '', 'have', 'I' ]

A lot happens in the final return step. First, the program uses the filter() method to make a new array with values that pass the defined tests. In the case of this algorithm, filter() is used to add just truthy values to the new array. Since empty strings ('') are known as falsy values in JavaScript, the filter disregards them. Finally, the join() method is used to combine each array element into a string, using a space as a separator between each word:

reverseArray.filter(x => x) = [ 'spaces', 'many', 'have', 'I' ]

Output (using join()) = "spaces many have I"

And just like that, the algorithm has returned our string meeting the requirements of the prompt. I completed this solution on LeetCode and I was pretty happy with the runtime and memory usage:

Same Problem, Different Requirements

After completing the previous challenge, I discovered a new version of the same problem with slightly different requirements. In this version, the algorithm had to return a string with the same number of whitespace as the original. This means that all whitespace leading, trailing, or in between words needed to be accounted for. Special characters are also allowed in this version (unlike the problem on LeetCode). Furthermore, it could not use either split() or reverse() to help in the process.

I'll be honest, this one took a little longer to crack. After slowly walking through the logic, it finally clicked and the answer came pretty quickly:

function reverseWordsUpdate(string) {
  let words = [];
  let currentWord = '';
  let stringLength = string.length + 1;

  for(var i = 0; i < stringLength; i++){         
     if(string[i] !== " " && i !== string.length){       
        currentWord += string[i];
     } else if(i === string.length){         
        words.unshift(currentWord);
     } else {
      words.unshift(currentWord);
      words.unshift(" ");
      currentWord = '';
     }
  } 

  return words.join("");
}

Similar to the previous solution, we start with a variable equal to an empty array. But then we have a variable called currentWord equal to an empty string. This variable comes into play later in the for loop (so stay tuned!). Finally, the variable stringLength is equal to its namesake, the length of the string input plus 1. We add 1 for looping purposes:

string = "Coding is the best!"
stringLength = 20

Then we enter the for loop, where one of the conditions is to increment the i variable until it's equal to the stringLength. You probably see now why we added 1 to the string's length: it ensures the loop iterates through each character in the string.

The loop contains several conditional statements. The first if statement checks to see if the character in the string isn't just whitespace and that it's not the last character in the string. If parameters return true, we add that character to the value of currentWord. Now you see the purpose of using currentWord: it allows the function to construct words from each character that isn't a whitespace. This is what it looks like as the loop executes:

i = 0 (currentWord = "C")
i = 1 (currentWord = "Co")
i = 2 (currentWord = "Cod")
i = 3 (currentWord = "Codi")
i = 4 (currentWord = "Codin")
i = 5 (currentWord = "Coding")

But what about when we hit the first whitespace? The first if statement will evaluate false and the program proceeds to the else if that follows. This statement checks to see if i is the last value in the string. If it is, this means we've hit the end of our string (or found the last word) and the program passes it into the words array using the unshift() method (why unshift? Keep reading!). But in this instance, since we are not at the end, this statement evaluates as false too.

The function then hits the final else statement, whose purpose is to take the completed string in currentWord and insert it into the words array. Now unlike my first solution, I decided to use the unshift() method as opposed to shift(). I realized that I could cut out the step of creating another reversed array by simply putting each new value in front of the previous one! After adding the word, the function also adds whitespace to the array and resets the value of currentWord back to an empty string, allowing the next word to be constructed:

words.unshift(currentWord) = [ 'Coding' ]
words.unshift(" ") = [ ' ', 'Coding' ]

Eventually the loop will run its course and the words array will be equal to [ 'best!', ' ', 'the', ' ', 'is', ' ', 'Coding' ]. Finally, just like in my previous answer, the join() method is used to create a string. Unlike my previous join(), I use an empty string ("") as a separator since the words array already contains a specific number of spaces that need to be returned:

Output = "best! the is Coding"

Conclusion

My biggest takeaway from the 'Reverse String' challenge is to search for different variations of the same problem in order to test your coding ability. It's easy to complete a challenge and memorize the code for solving it, but such rigidity hampers the process of thinking critically. It's possible a technical interviewer will take a classic problem and put a unique spin on it, especially when other companies frequently use the same questions. In these cases, it's important to be flexible and walk-through how the logic of the algorithm will change given the new requirements. You've only truly solved a problem when you understand how each part works, not by memorizing an algorithm's structure.

Trust me, I've been guilty of taking the memorization route and it came back to bite me when I was forced to be flexible. If anything I'm taking this practice time as an opportunity to focus on the how and why of the algorithm. I've found that when I do this I can often discover a solution or the next step of the process if I'm stuck. That being said, I'm still a work in progress and I've definitely run into some problems where I've had to wave the white flag. But the important thing I keep telling myself is to understand how the code works, and that's the best advice I can offer to anyone practicing algorithms.