RSS

EPI 6.19 – Reversing words in a sentence

01 Feb

Problem

Reverse the words in a sentence.

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.

In haskell, the recursive solution would be:

reverse_words :: [Char] -> [Char]
reverse_words [] = []
reverse_words xs = initial_spaces ++ (reverse after_spaces) ++ reverse_words remaining
    where
        initial_spaces = takeWhile isSpace xs
        spaces_dropped = dropWhile isSpace xs
        after_spaces = takeWhile (\x -> not (isSpace x)) spaces_dropped
        remaining = drop (length after_spaces) spaces_dropped

This is clearly not O(1) in space usage. The constant space solution would require maintaining array structures and swapping entries within the array.

About these ads
 

Tags: , , ,

One response to “EPI 6.19 – Reversing words in a sentence

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
Follow

Get every new post delivered to your Inbox.

%d bloggers like this: