Reverse Words in a String

The question

Given an input string, reverse all the words. To clarify, input: “Interviews are awesome!” output: “awesome! are Interviews”. Consider all consecutive non-whitespace characters as individual words. If there are multiple spaces between words reduce them to a single white space. Also remove all leading and trailing whitespaces. So, the output for ” CS degree”, “CS degree”, “CS degree “, or ” CS degree ” are all the same: “degree CS”.

My solution

This question feels a little tricky because it looks easy but it makes me think that there are implications with the way strings are handled that should be taken into account. For a simple approach I would do this:

– Create an empty string

– Start at the last character

– If it is and empty space keep moving towards the first character until you find a letter.

– If it is a letter set a variable to the index of that letter

– Keep moving left until you find a space or the string ends

– When that happens grab all characters from that point until the first letter you found and add them to previously created string

– Repeat until you reach the end of the string

The best solution

After taking a look at the best solution I realized that my solution wasn’t that bad but there is a way to solve the problem without using extra space: Reverse all the characters in the string, then reverse the letters of each individual word. This could be done inline if it wasn’t because in JS strings are immutable, which means:

1
2
3
var s = 'asdf';
s[0] = 'b';
console.log(s); // Prints asdf

With this in mind this is my solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
function reverse(input) {
  var string = '';
  var end = null;

  // Start at the end
  for (var i = input.length; i !== 0; i--) {
    if (input[i - 1] !== ' ') {
      // If a letter was found and end has not been set (we are not in the
      // middle of a word) then set end
      if (end === null) {
        end = i - 1;
      }
    } else {
      // If this is a space and end is set (We were inside a word). Then add all
      // characters of the word to the string
      if (end !== null) {
        // Add a space as separator for all but the first string
        if (string.length) {
          string += ' ';
        }

        for (var j = i; j <= end; j++) {
          string += input[j];
        }

        end = null;
      }
    }
  }

  return string;
}

function test() {
  if ('world pretty hello' === reverse('  hello pretty  world      ')) {
    console.log('success');
  }
}

test(); // Prints success