LESSON 228 OF 347 · TWO POINTERS

Reverse Words in a String in C#: Reverse Twice, In Place on a char Array

Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by one space for simplicity.

Return a string of the words in reverse order concatenated by a single space.

Example:

Input:  input = "sky is blue"

Output:  "blue is sky"

STEP 1 OF 18

Guided

Ctrl + Enter to check

C# · TWO POINTERS

Reverse Words in C#, explained

Problem overview

ReverseWords receives a string input of words separated by single spaces and returns the words in reverse order, joined by single spaces. For "sky is blue" the result is "blue is sky". A word is a run of non-space characters, and the statement guarantees exactly one space between neighbouring words.

Approach

A direct solution splits the string into words, reverses that list and joins it back. This lesson does it with swaps on a character array, in two passes of the same helper:

Reverse the whole string. The words are now in the opposite order, but each one is spelled backwards.
Reverse each word on its own, so it is spelled correctly again.

For "sky is blue", the first pass produces "eulb si yks". The second pass finds the words eulb, si and yks and reverses each, giving "blue is sky". Because the spaces are single and sit between words, they land in the right places after the first reversal and are never moved again.

Both passes use one helper, Reverse(arr, i, j), which reverses the part of the array from index i to index j inclusive. That helper in turn uses Swap(arr, i, j). Strings are immutable in C#, which is why the work happens on a char[] copy.

Following the word loop

After the first reversal the array holds "eulb si yks", which has 11 characters. The loop starts with i = 0. The inner loop moves j forward until it finds the space at index 4, so the word is indexes 0 to 3, and Reverse(arr, 0, 3) turns eulb into blue. Then i becomes 5. The next word, si, occupies indexes 5 and 6, and the space is at index 7. The last word starts at index 8. There j stops because it reached 11, the array's length, not because of a space, and Reverse(arr, 8, 10) fixes yks. Then i becomes 12 and the outer loop ends.

This is why the loop condition on j checks the length as well as the space: the last word has no space after it.

Step by step

Copy the characters into arr with input.ToCharArray(), a new array that can be changed.
Reverse everything by calling Reverse(arr, 0, arr.Length - 1).
Track the current word's start in i, beginning at 0.
Loop while i < arr.Length, one iteration per word.
Find the word's end. Start j at i and advance it while j < arr.Length and arr[j] isn't a space. Check the length first: && stops at the first false side, so arr[j] is never read past the end.
Reverse the word. It spans i to j - 1, because j is the space after it or the end of the array.
Skip the space by setting i to j + 1.
Return new string(arr) after the loop.
Write Reverse. While i < j, call Swap(arr, i, j), then move i up and j down. Both parameters are copies, so changing them doesn't affect the caller's variables.
Write Swap. Save arr[i] in temp, copy arr[j] into arr[i], then put temp into arr[j].

The solution in C#

class Solution {
    public void Swap(char[] arr, int i, int j) {
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public void Reverse(char[] arr, int i, int j) {
        while (i < j) {
            Swap(arr, i, j);
            i++;
            j--;
        }
    }

    public string ReverseWords(string input) {
        char[] arr = input.ToCharArray();
        Reverse(arr, 0, arr.Length - 1);
        int i = 0;
        while (i < arr.Length) {
            int j = i;
            while (j < arr.Length && arr[j] != ' ') {
                j++;
            }
            Reverse(arr, i, j - 1);
            i = j + 1;
        }
        return new string(arr);
    }
}

C# details:

Arrays are reference types. Reverse and Swap return void, yet the caller sees the changes, because they receive a reference to the same array. The integers i and j are passed by value, so the loop inside Reverse doesn't alter the caller's own i and j.
Char literals use single quotes. ' ' is one space character. A string literal " " would not compare with a char using !=.
A method named Reverse is fine, since it is a member of Solution. Inside the class, the call Reverse(arr, ...) resolves to it.
The final conversion. new string(arr) builds a string from all the characters in the array. The original input is unchanged.

Complexity

Time: O(n). The whole-string reversal touches each character once. The word loop moves j across every character once in total, and reversing the words touches each of those characters once more. Altogether it is a few linear passes.

Space: O(n). The character array is a copy of the input. The swaps themselves use constant extra memory, so the array is the only linear cost.

Edge cases and common mistakes

A single word. "hi" is reversed to "ih" and the word pass restores "hi".
The empty string. Reverse(arr, 0, -1) does nothing because 0 < -1 is false, and the word loop never runs. The result is an empty string.
Checking arr[j] before j < arr.Length. At the last word j reaches the length, and the read throws IndexOutOfRangeException.
Reversing i to j instead of i to j - 1. That includes the space after the word in the swap and moves it into the word's first position.
Extra spaces. The statement promises single spaces. If the input had leading, trailing or repeated spaces, this code would keep them, mirrored in position, instead of collapsing them. For " a" it returns "a ".
Skipping the second pass. The whole-string reversal alone gives "eulb si yks". Each word needs its own reversal.

Testing

"sky is blue" gives "blue is sky".
"a b" gives "b a".
"hi" gives "hi".
"" gives "".

Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free