Reverse Words
March 8, 2011
Our strategy will be two-fold: first, reverse the entire string, then reverse each maximal run of non-space characters. Here is a function to reverse a substring in-place, from lo inclusive to hi exclusive:
(define (string-reverse! s lo hi)
(let loop ((lo lo) (hi (- hi 1)))
(if (< hi lo) s
(let ((t (string-ref s lo)))
(string-set! s lo
(string-ref s hi))
(string-set! s hi t)
(loop (+ lo 1) (- hi 1))))))
It’s easy enough to find the next space, returning the string-length if there is no space before the end of the string:
(define (next-space s len i)
(do ((i i (+ i 1))) ((or (= i len) (char=? (string-ref s i) #\space)) i)))
The following function executes the strategy. First the entire string is reversed by the call (string-reverse! s 0 len) in the initialization of the loop. Then the loop repeatedly reverses substrings from lo to hi, resetting lo to hi+1 and hi to (next-space s len (+ hi 1)) each time through the loop. Since the loop is executed once for each space, the final word in the loop must be handled explicitly in the loop termination:
(define (reverse-words s)
(let ((len (string-length s)))
(let loop ((s (string-reverse! s 0 len)) (lo 0) (hi (next-space s len 0)))
(if (= len hi) (string-reverse! s lo hi)
(loop (string-reverse! s lo hi) (+ hi 1) (next-space s len (+ hi 1)))))))
Here are some samples:
> (reverse-words "")
""
> (reverse-words " ")
" "
> (reverse-words " ")
" "
> (reverse-words "hello")
"hello"
> (reverse-words "hello ")
" hello"
> (reverse-words " hello")
"hello "
> (reverse-words "the quick brown fox")
"fox brown quick the"
> (reverse-words "the quick brown fox")
"fox brown quick the"
> (reverse-words "the quick brown 42 fox!")
"fox! 42 brown quick the"
You can run the program at http://programmingpraxis.codepad.org/NYohlcHq. You may note that the reverse-words function given there differs slightly from the one shown above. The difference is because MzScheme, which is used at Codepad, has two types of strings, mutable and immutable, whereas Standard R5RS Scheme has only one type of string, which is mutable. In MzScheme, an input string such as "" or "the quick brown fox" is always immutable; the construction (substring s 0) converts the string to mutable.
Programming Praxis 
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[…] today’s Programming Praxis exercise, we’re revisiting the well-known interviewing problem of […]
My 2 cents in python:
def reverseWords(s): l = str.split(s, ' ') list.reverse(l) return ' '.join(l)arf my bad, I used builtin functions….sorry
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()) or2. 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))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;
}
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 outIf 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)))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.
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])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; } }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!"reverseWord = (concat.reverse.(groupBy noChar))
where
noChar ‘ ‘ ‘ ‘ = True
noChar x y = (not.isSpace) x && (not.isSpace) y
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)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 ausimport 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) testDatagive a answer using looping simply
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
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!"))