Given an array of characters which forms a sentence of words, give an efficient algorithm to reverse the order of the words (not characters) in it.
Example input and output:
>>> reverse_words("this is a string")
'string a is this'
It should be O(N) time and O(1) space (split() and pushing on / popping off the stack are not allowed).
The puzzle is taken from here.
You would use what is known as an iterative recursive function, which is O(N) in time as it takes N (N being the number of words) iterations to complete and O(1) in space as each iteration holds its own state within the function arguments.
(define (reverse sentence-to-reverse)
(reverse-iter (sentence-to-reverse ""))
(define (reverse-iter(sentence, reverse-sentence)
(if (= 0 string-length sentence)
reverse-sentence
( reverse-iter( remove-first-word(sentence), add-first-word(sentence, reverse-sentence)))
Note: I have written this in scheme which I am a complete novice, so apologies for lack of correct string manipulation.
remove-first-word finds the first word boundary of sentence, then takes that section of characters (including space and punctuation) and removes it and returns new sentence
add-first-word finds the first word boundary of sentence, then takes that section of characters (including space and punctuation) and adds it to reverse-sentence and returns new reverse-sentence contents.
Push each word onto a stack. Pop all the words off the stack.