The Algorithm for Reversing A Sentence

I did a practice interview on Pramp this week. It didn’t go super well — which is frustrating because in retrospect it wasn’t that difficult of a question. Let’s jump in.

I was asked a question called “Sentence Reverse.” You are given an array of characters “s” that “consists of sequences of characters separated by space characters. Each space-delimited sequence of characters defines a word.” So, you are given something like this:

s[] = “perfect makes practice”

You are asked to “implement a function ‘reverse_words’ that reverses the order of the words in the array in the most efficient manner.” So the desired output if given the input above would be:

s[] = “practice makes perfect”

With regards to edge cases, there may be an empty array, an array containing only spaces, a one word array, multiple spaces between words, and etc.

The best way to solve this problem is by first reversing each of the words in the array:

s[] = “ecitcarp sekam tcefrep”

And then reversing each of the individual words:

s[] = “practice makes perfect”

Let’s start to code.

First, let’s think about our main function. We’ll want to initialize the string literal that we’ll be reversing. We’ll then want to pass the address of the string literal to a function that will reverse every word in the string. Our main function could look something like this:

I include the print statements I used to debug for reference.

When we call reverse_words(s) we are actually passing the memory address of the first character in our string to the function. This is handy because this way, our helper functions do not have to return anything back to main() since main() has a reference to the data that the helper functions are manipulating.

Next, let’s write reverse_words(). Since the first thing we need to accomplish is reverse each word in the string, reverse_words() will be in charge of, for each word it encounters, getting a pointer set to the beginning and end of the word. Once these pointers are set, we can call reverse() on each word which will actually reverse each of the characters in the string:

Notice how reverse_words() walks through the string s:

1. First, we set our while loop to run until the value of the address that temp is pointing to is NULL.

2. Second, we increment the address that temp is pointing to and then check if now we are pointing at a NULL byte. Notice this is a case where a while loop seems to be a better fit than a for loop as we want to increment temp before we encounter our logic in the loop body — not afterwards which is typically what would happen in a for or do-while loop.

- If we are pointing at a NULL byte than we have reached the end of our character array. All we have to do now is reverse the last word in the array, wait for our while loop to terminate, and call reverse (line 45) and reverse the entire string.

3. Next, we check if temp is pointing to a space character.

- If we are pointing to a space character, then we’ve found the end of another word in our string. We will need to call reverse using our pointer to the beginning of the string (word_begin) and temp-1 which represents the last character in the string.

- After we reverse that word, we need to set our new word begin to temp+1 which represents the first character in the next word in our string and then continue with the loop.

4. If temp is not pointing to a NULL byte or space character, all we do in each loop iteration is increment the temp pointer through the letters in the word.

Now let’s take a look at how reverse() actually reverses characters in the words we pass it:

So, while the address of begin is less than the address of end, we will run a while loop that:

// Let’s imagine that we’re reversing the string “perfect”

1. Copies the value of ‘p’ into a char variable called temp.

2. Changes the value at the address that begin was pointing to (which used to be ‘p’) to the value at the address that end is pointing to (which is ‘t’). We can test this by printing the string using our character pointer save which points to the beginning of the string. The string should now read “terfect.”:

The post-fix increment operator is than applied. Now, begin is pointing to the second character in our string which is ‘e’:

3. The character saved in temp is than assigned to the address saved in the pointer end. The word should now read “terfecp”:

The post-fix decrement operator is than applied and end now points to the second to last character in our word ‘c’:

This loop will continue until the address that begin is pointing to is greater than that of end:

With regards to time and space complexity this algorithm is O(n) for both where n represents the number of characters in the string.

That is how you can reverse a sentence in a low-level language like C.