Problem overview
The method ReverseWords takes a string, input, made of words separated by exactly one space, and returns the same words in reverse order, again separated by single spaces. A word is a run of non-space characters. For "sky is blue" the result is "blue is sky".
Only the order of the words changes. Each word keeps its letters in the original order, which is what separates this problem from reversing the whole string.
Approach: split, reverse the array, join
Reversing the whole string character by character would give "eulb si yks": the words appear in the right order but are spelled backwards. To avoid that, work with words as units:
- Cut the string into an array of words.
- Reverse the array.
- Glue the words back together with spaces.
Because the problem guarantees exactly one space between words, splitting on a single space gives exactly the words, with no empty pieces to worry about.
Step by step
- Split.
input.Split(' ')returns astring[]. The argument is achar, written with single quotes. Storing the result withvarlets the compiler infer the array type. - Reverse in place.
Array.Reverse(words)is a static method that rearranges the array it is given and returns nothing, so don't assign its result to a variable. - Join and return.
string.Join(" ", words)puts one space between consecutive elements, with none at the start or the end. The separator comes first and the array second.
The solution in C#
class Solution {
public string ReverseWords(string input) {
var words = input.Split(' ');
Array.Reverse(words);
return string.Join(" ", words);
}
}
Some details about the C# involved:
Array.Reverseis static. It is called on theArrayclass with the array as an argument, not aswords.Reverse(). Written with the dot,words.Reverse()would refer to LINQ's version, which returns a new sequence and leaves the array unchanged, and it also needsusing System.Linq;.Splitdoesn't change the original. The string stays as it was. The new array contains separate string objects.- Empty pieces are kept. With the default options, two adjacent separators produce an empty string between them:
"a b".Split(' ')has three elements,"a",""and"b". For input that may contain repeated spaces, passStringSplitOptions.RemoveEmptyEntriesas a second argument. This lesson's input never needs it. string.Join. Besides arrays, it accepts any sequence of strings. It is also cheaper than adding the words one by one with+=, which would copy the growing text each time.
Complexity
Time: O(n), where n is the length of the string. Split scans the characters once, Array.Reverse swaps each word reference at most once, and Join copies every character once into the result.
Space: O(n). The array of words together holds all the characters again, and so does the final string. The reversal itself swaps entries inside the array and needs no further memory.
Edge cases and common mistakes
- A single word.
"one"splits into one element and comes back as"one". - An empty string.
"".Split(' ')returns an array with one empty string, and joining it gives"", so the method returns an empty string without failing. - Reversing characters instead of words. Reversing the string would reverse every word's spelling too.
- Splitting on
" "versus' '. Both overloads exist in current .NET, and with one separator they give the same pieces. Thecharform is the one this lesson uses. - Assigning the result of
Array.Reverse.var r = Array.Reverse(words);doesn't compile, because the method returns nothing. - Extra spaces in other inputs. If a problem allowed leading, trailing or repeated spaces, the empty pieces from
Splitwould end up in the output as extra spaces, and you would needRemoveEmptyEntries.
Testing
"sky is blue"gives"blue is sky"."one"gives"one"."hello world"gives"world hello"."a b c d"gives"d c b a".