Problem: ¶

Reverse the words in a sentence, eg:

hello world -> world hello

Solution: ¶

We can define a word as any substring separated by one or more spaces. To do this on constant space, simply reverse the entire sentence, and then reverse each word within.

A recursive solution would be:

1reverse_words :: [Char] -> [Char]
2reverse_words [] = []
3reverse_words xs = initial_spaces ++ (reverse after_spaces) ++ reverse_words remaining
4    where
5        initial_spaces = takeWhile isSpace xs
6        spaces_dropped = dropWhile isSpace xs
7        after_spaces = takeWhile (\x -> not (isSpace x)) spaces_dropped
8        remaining = drop (length after_spaces) spaces_dropped

This is clearly not O(1) in space usage. The constant space solution would perform an in-place swapping of characters within the input array.