Reverse Words

March 8, 2011

After we solved the reverse-words problem in an exercise a few weeks ago, a reader complained that the suggested solution was too simple because it used library functions to split the words and later to rejoin them; he also thought the exercise should include a restriction that the string had to be reversed in-place. I’m not sure about either of the objections, but we’ll take the opportunity to revisit a classic interview question. We’ll also eliminate the letters-only and single-space-between-words restrictions of the original exercise from Google. Thus, here are some sample inputs and their associated outputs; note especially the placements of leading and trailing spaces:

"" => ""
" " => " "
"  " => "  "
"hello" => "hello"
"hello " => " hello"
" hello" => "hello "
"the quick brown fox" => "fox brown quick the"
"the quick  brown fox" => "fox brown  quick the"
"the quick  brown 42 fox!" => "fox! 42 brown  quick the"

Your task is to write a reverse-words function given the definition and restrictions stated above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

19 Responses to “Reverse Words”

  1. My Haskell solution (see http://bonsaicode.wordpress.com/2011/03/08/programming-praxis-reverse-words/ for a version with comments):

    import Data.Array.IO
    
    switch :: (MArray a e m, Ix i) => i -> i -> a i e -> m ()
    switch i j a = do x <- readArray a i
                      writeArray a i =<< readArray a j
                      writeArray a j x
    
    revRange :: Int -> Int -> IOArray Int a -> IO (IOArray Int a)
    revRange i j a = mapM_ (\n -> switch n (j+i-n) a) [i..div (i+j) 2] >> return a
    
    reverseWords :: String -> IO String
    reverseWords xs = do a <- newListArray (0, length xs - 1) xs
                         (s,e) <- getBounds a
                         f 0 e =<< revRange s e a where
        f i e a = if i > e then getElems a else nextSpace i e a >>=
                     \s -> f (s+1) e =<< revRange i (s-1) a
        nextSpace i e a = if i > e then return i else readArray a i >>= \c ->
                          if c == ' ' then return i else nextSpace (i+1) e a
    
  2. [...] today’s Programming Praxis exercise, we’re revisiting the well-known interviewing problem of [...]

  3. My 2 cents in python:

    def reverseWords(s):
        l = str.split(s, ' ')
        list.reverse(l)
        return ' '.join(l)
    
  4. arf my bad, I used builtin functions….sorry

  5. Graham said

    Python strings are immutable, so we can’t change them in place. I came up with
    two options, neither of which are terribly satisfactory:
    1. build a new string with the slice reversed (reverse_slice()) or
    2. turn our string into a list and work on that (rev_slice_list()
    like Remco’s solution with arrays), but that still creates a new object
    and requires converting back to a string.
    I decided to emulate the official solution’s sample tests somewhat closely.

    #!/usr/bin/env python
    
    
    def reverse_slice(s, i, j):
        r = s[:i]
        for k in xrange(i, j):
            r += s[j - k + i - 1]
        r += s[j:]
        return r
    
    
    def rev_slice_list(s, i, j):
        s = list(s)
        for k in xrange((j - i) / 2):
            s[i + k], s[j - k - 1] = s[j - k - 1], s[i + k]
        r = ""
        for l in s:
            r += l
        return r
    
    
    def find_space(s, i):
        for j in xrange(i, len(s)):
            if s[j] == ' ':
                return j
        return len(s)
    
    
    def reverse_words(s):
        r = reverse_slice(s, 0, len(s))     # or rev_slice_list(s, 0, len(s))
        i, j = 0, find_space(r, 0)
        while j is not len(r):
            r = reverse_slice(r, i, j)      # or rev_slice_list(s, i, j)
            i, j = j + 1, find_space(r, j + 1)
        return reverse_slice(r, i, j)
    
    
    if __name__ == "__main__":
        for s in ["", " ", "  ", "hello", "hello ", " hello",
                    "the quick brown fox", "the quick  brown fox",
                    "the quick  brown 42 fox!"]:
            print '> (reverse-words "%s")\n"%s"' % (s, reverse_words(s))
    
  6. Jebb said

    I actually wrote that a couple of days ago and tried submitting it to the other exercise, but for some reason WordPress didn’t like it (it never appeared in the list of comments, and I got a “comment already submitted” error when I tried to re-submit it). [ Sorry. It went to the spam folder for some reason, along with three other comments on that post. All have now been retrieved. Phil ]

    Anyway, in C, first reversing the letters word by word, then reversing the whole string (please excuse the puerile bit of fun with macros). It doesn’t quite do what’s asked here, as it will treat punctuation the same as whitespace, but it’s close enough:

    #define is_word_char(A) \
    (((A) >= ‘a’ && (A) <= ‘z’) || \
    ((A) >= ‘A’ && (A) <= ‘Z’) || \
    ((A) >= ’0′ && (A) <= ’9′))

    /* —————————–
    * Questionable macro implementation of swap,
    * careful when reusing,
    * definitely not threadsafe */
    #define swapchar(A,B) \
    do { \
    tmp_swap_char = *(A); \
    *(A) = *(B); \
    *(B) = tmp_swap_char; \
    } while (0)
    char tmp_swap_char;
    /* —————————– */

    void reverse_from_to(char *from, char *to)
    {
    // Reverses part of a string, between *from and *to
    int i;
    for (i = 0; i < (to – from + 1) / 2; i++){
    swapchar(from + i, to – i);
    }
    }

    char* reverse_words_in_string(char *str)
    {
    char *cp; //points to character within a word
    char *wp = str; //points to start of a word
    /* We’ll first reverse the letters in each word within the string str */
    while (*wp != ‘\0’) {
    if (is_word_char(*wp)) {
    cp = wp;
    while (is_word_char(*(cp + 1)))
    cp++;
    reverse_from_to(wp, cp);
    wp = cp;
    }
    wp++;
    }
    /* Now simply reverse the whole string again to finish the job */
    reverse_from_to(str, str + strlen(str) – 1);
    return str;
    }

  7. Mike said

    As Graham pointed out above, strings are immutable in Python. So, I just eliminated the built-in functions that made the earlier exercise too easy.

    Basic strategy is to start at the end and scan the string backwards to identify runs of similar (space or non-space) characters.

    First solution uses built in ‘len’ and ‘isspace’, because most languages have equivalents. Second version omits even those built-ins.
    If you don’t like (s[b-1] in ‘ \t’) replace it with (s[b-1]==’ ‘ or s[b-1]==’\t’).

    def revword(s):
        '''
        >>> revword(" the quick  brown 42 fox!")
        'fox! 42 brown  quick the '
        '''
        b = e = len(s)
        out = ''
        while e:
            while b and s[b-1].isspace() == s[e-1].isspace():
                b -= 1
    
            out += s[b:e]
            e = b
    
        return out
    
    def revword2(s):
        '''
        >>> revword2(" the quick  brown 42 fox!")
        'fox! 42 brown  quick the '
        '''
    
        e = 0
        while s[e:e+1]:
            e += 1
            
        b = e
        out = ''
        
        while e:
            while b and (s[b-1] in ' \t') == (s[e-1] in ' \t'):
                b -= 1
    
            out += s[b:e]
            e = b
            
        return out
    
  8. Mike said

    If I asked a job applicant to solve this problem, I would expect them to use the features of their chosen programming language.

    For Python I would expect something like this:

    import re
    
    def revwords(s):
        return ''.join(reversed(re.split(r'(\s+)',s)))
    
  9. programmingpraxis said

    Mike: As I said in the first paragraph of the exercise, I wasn’t sure about either of the reader’s objections. But as an interview question, sometimes you just have to go with what the interviewer wants; think of today’s exercise as the follow-up question from the interviewer after you have given the straight forward answer. And it does make for a good exercise. I got it wrong the first time I wrote it, an off-by-one error in resetting lo and hi for the next step. Maybe the next time I go on a job interview, and get this question, I’ll get it right.

  10. Lautaro Pecile said
    def split(s):
        l = []
        for c in s:
            if c == ' ':
                if l:
                    yield ''.join(l)
                    l = []
                yield c
            else:
                l.append(c)
    
    
    def revwords(s):
        return ''.join(list(split(s))[::-1])
    
    
  11. Mike said

    Haven’t used C seriously in at least 15 years, so I was a bit rusty. But after a few trys I came up with the following routine. It doesn’t use any library functions.

    /*
       Reverse the order of words in a string.
    
       Works by rotating strings so that the last char moves to the front.  Initially, the entire string is rotated.  
       When a change between space/non-space or non-space/space is detected, the start of the substring being rotated is updated.
    */
    void revwords(char *s) {
       char *c;
       char *e;
       char  t, *p, *q;
    
       for (e = s; *(e+1); e++) 
          ;
    
       for (c = s; *s; s++) {
          if ((*c==' ') != (*e==' ')) 
             c = s;
          
          t = *e;
          for (p = e, q = e-1; p > c; *p-- = *q--) ;
          *c = t;
       }
    }
    
  12. Khanh Nguyen said
    
    let reverse_a_word (s:string) =
        let t = s.ToCharArray() |> Array.rev 
        string (System.String(t))
    
    let reverse_words (s:string) =    
    
        let r = s.ToCharArray() 
                |> List.ofArray 
                |> List.rev 
                |> List.fold (fun (w:string, res:string) c -> 
                                    if c = ' ' then 
                                        ("",res + (reverse_a_word w) + (string c)) 
                                    else (w + (string c), res))
                   ("","") 
        
        (snd r) + (reverse_a_word (fst r))
                  
    reverse_words "the quick  brown fox"
    reverse_words "hello "
    reverse_words " hello"
    reverse_words "the quick brown fox"
    reverse_words "the quick  brown fox"
    reverse_words "the quick  brown 42 fox!"
  13. Umur Gedik said

    reverseWord = (concat.reverse.(groupBy noChar))
    where
    noChar ‘ ‘ ‘ ‘ = True
    noChar x y = (not.isSpace) x && (not.isSpace) y

  14. Rainer said

    My try in REXX

    
    zwei:                                                         
        parse arg text                                            
        aus = ''                                                  
        lwort = ''                                                
        do x = length(text) to 1 by -1                            
            cp = substr(text,x,1)                                 
            select                                                
                when cp == ' ' then do                            
                    if length(lword) == 0 then aus = aus||cp      
                    else aus = aus||reverse(lwort)||cp            
                    lwort = ''                                    
                    end                                           
                otherwise lwort = strip(lwort)||cp                
            end                                                   
        end                                                       
        return aus||reverse(lwort)       
    
    
  15. Rainer said

    with self-made reverse()

    
    zwei: procedure                                               
        parse arg text                                            
        aus = ''                                                  
        lwort = ''                                                
        do x = length(text) to 1 by -1                            
            cp = substr(text,x,1)                                 
            select                                                
                when cp == ' ' then do                            
                    if length(lword) == 0 then aus = aus||cp      
                    else aus = aus||drei(lwort)||cp               
                    lwort = ''                                    
                    end                                           
                otherwise lwort = strip(lwort)||cp                
            end                                                   
        end                                                       
    
        return aus||drei(lwort)                                   
                                                                  
    drei: procedure                                                 
        parse arg text                                              
        aus = ''                                                    
        do x = length(text) to 1 by -1                              
            if length(aus) == 0 then aus = substr(text,x,1)         
                                else aus = aus||substr(text,x,1)    
        end                                                         
        return aus                                                  
                                                                  
    
  16. fire said
    import Prelude hiding (reverse)
    import Control.Monad (mapM_)
    
    reverse :: String -> String
    reverse = concat . revsplit
        where revsplit :: String -> [String]
              revsplit = foldl f []
                where f :: [String] -> Char -> [String]
                      f [] c = [[c]]
                      f acc ' ' = " " : acc
                      f acc@(" ":_) c = [c] : acc
                      f (x:xs) c = (x ++ [c]) : xs
    
    testData =
        [ ("", "")
        , (" ", " ")
        , ("  ", "  ")
        , ("hello", "hello")
        , ("hello ", " hello")
        , (" hello", "hello ")
        , ("the quick brown fox", "fox brown quick the")
        , ("the quick  brown fox", "fox brown  quick the")
        , ("the quick  brown 42 fox!", "fox! 42 brown  quick the")
        ]
    
    testReverse :: (String -> String) -> (String, String) -> IO ()
    testReverse rf (a, b) = do
        let ra = rf a
        if ra == b then putStrLn $ "pass: '" ++ a ++ "'"
                   else putStrLn $ "fail: '" ++ a ++ "' => '" ++ ra ++ "'"
    
    main :: IO ()
    main = mapM_ (testReverse reverse) testData
    
  17. rv singh said

    give a answer using looping simply

  18. rv singh said

    i cn die 4 learning alll the languages of computer …i want to become a sofware developer wana make everything related to programming ….m a engineering student plz help me sir how can i improve my programming skills

  19. My solution in Python:

    
    #Reversing string in python
    
    def Reverse(Str):
    
    	if len(Str.split()) == 1:
    	
    		print(len(Str.split()))
    	
    		return Str.strip(" ")
    		
    	else:
    	
    		return ' '.join(Str.split(' ')[::-1])
    
    def Join_Str(Str):
    
    	if Str == "":
    	
    		return '"' + '"'
    		
    	elif Str == " ":
    	
    		return '" "'
    		
    	else:
    
    		result = Reverse(Str)
    		print(result)
    		
    	if Str[0] == ' ' and Str[-1] == ' ':
    	
    		return ' " ' + result + ' " '
    	
    	elif Str[0] == ' ':
    	
    		return '"'+ result + ' "' 
    
    				
    	elif Str[-1] == " ":
    	
    		print(Str[-1])
    	
    		return '" ' + result + '"'
    			
    	else:
    	
    		return '"' + result + '"'
    	
    
    print(Join_Str("the quick  brown 42 fox!"))
    
    

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.

Join 632 other followers

%d bloggers like this: