Given an array of characters which form a sentence of words, give an efficient algorithm to reverse the order of the words (not characters) in it.

Question

Example input and output:

>>> reverse_words("this is a string")
'string a is this'

It should be O(N) in time and O(1) in space (split() and pushing on/poping of stack are not allowed).

The puzzle is taken from here

Answer 1

In pseudo code:

reverse input string
reverse each word (you will need to find word boundaries)

Answer 2

Push each word onto a stack. Pop all the words off the stack.

Answer 3

In C: (C99)

#include <stdio.h>
#include <string.h>

void reverseString(char* string, int length)
{
    char swap;
    for (int i = 0; i < length/2; i++)
    {
     swap = string[length - 1 - i];
     string[length - 1 - i] = string[i];
     string[i] = swap;
    } 
}

int main (int argc, const char * argv[]) {
    char teststring[] = "Given an array of characters which form a sentence of words, give an efficient algorithm to reverse the order of the words (not characters) in it.";
    printf("%s\n", teststring);
    int length = strlen(teststring);
    reverseString(teststring, length);
    int i = 0;
    while (i < length)
    {
     int wordlength = strspn(teststring + i, "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz");
     reverseString(teststring + i, wordlength);
     i += wordlength + 1;
    }
    printf("%s\n", teststring);
    return 0;
}

This gives output:

Given an array of characters which form a sentence of words, give an efficient algorithm to reverse the order of the words (not characters) in it.

.it in )characters not( words the of order the reverse to algorithm efficient an give ,words of sentence a form which characters of array an Given

This takes at most 4N time, with small constant space. Unfortunately, It doesn't handle punctuation or case gracefully.

Answer 4

O(N) in space and O(N) in time solution in Python:

def reverse_words_nosplit(str_):
  """
  >>> f = reverse_words_nosplit
  >>> f("this is a string")
  'string a is this'
  """
  iend = len(str_)
  s = ""
  while True:
    ispace = str_.rfind(" ", 0, iend)
    if ispace == -1:
      s += str_[:iend]
      break
    s += str_[ispace+1:iend]
    s += " "
    iend = ispace
  return s

Answer 5

A solution in C/C++:

void swap(char* str, int i, int j){
    char t = str[i];
    str[i] = str[j];
    str[j] = t;
}

void reverse_string(char* str, int length){
    for(int i=0; i<length/2; i++){
        swap(str, i, length-i-1);
    }
}
void reverse_words(char* str){
    int l = strlen(str);
    //Reverse string
    reverse_string(str,strlen(str));
    int p=0;
    //Find word boundaries and reverse word by word
    for(int i=0; i<l; i++){
        if(str[i] == ' '){
            reverse_string(&str[p], i-p);
            p=i+1;
        }
    }
    //Finally reverse the last word.
    reverse_string(&str[p], l-p);
}

This should be O(n) in time and O(1) in space.

Edit: Cleaned it up a bit.

The first pass over the string is obviously O(n/2) = O(n). The second pass is O(n + combined length of all words / 2) = O(n + n/2) = O(n), which makes this an O(n) algorithm.

Answer 6

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.

Answer 7

A C++ solution:

#include <string>
#include <iostream>
using namespace std;

string revwords(string in) {
    string rev;
    int wordlen = 0;
    for (int i = in.length(); i >= 0; --i) {
        if (i == 0 || iswspace(in[i-1])) {
            if (wordlen) {
                for (int j = i; wordlen--; )
                    rev.push_back(in[j++]);
                wordlen = 0;
            }
            if (i > 0)
                rev.push_back(in[i-1]);
        }
        else
            ++wordlen;
    }
    return rev;
}

int main() {
    cout << revwords("this is a sentence") << "." << endl;
    cout << revwords("  a sentence   with extra    spaces   ") << "." << endl;
    return 0;
}

Answer 8

pushing a string onto a stack and then popping it off - is that still O(1)? essentially, that is the same as using split()...

Doesn't O(1) mean in-place? This task gets easy if we can just append strings and stuff, but that uses space...

EDIT: Thomas Watnedal is right. The following algorithm is O(n) in time and O(1) in space:

1. reverse string in-place (first iteration over string)
2. reverse each (reversed) word in-place (another two iterations over string)
   1. find first word boundary
   2. reverse inside this word boundary
   3. repeat for next word until finished

I guess we would need to prove that step 2 is really only O(2n)...

Answer 9

using System;

namespace q47407
{
    class MainClass
    {
     public static void Main(string[] args)
     {
      string s = Console.ReadLine();
      string[] r = s.Split(' ');
      for(int i = r.Length-1 ; i >= 0; i--)
       Console.Write(r[i] + " ");
      Console.WriteLine();

     }
    }
}

edit: i guess i should read the whole question... carry on.

Answer 10

#include <string>
#include <boost/next_prior.hpp>
void reverse(std::string& foo) {
    using namespace std;
    std::reverse(foo.begin(), foo.end());
    string::iterator begin = foo.begin();
    while (1) {
        string::iterator space = find(begin, foo.end(), ' ');
        std::reverse(begin, space);
        begin = boost::next(space);
        if (space == foo.end())
            break;
    }
}

Answer 11

@Daren Thomas

Implementation of your algorithm (O(N) in time, O(1) in space) in D (Digital Mars):

#!/usr/bin/dmd -run
/**
 * to compile & run:
 * $ dmd -run reverse_words.d
 * to optimize:
 * $ dmd -O -inline -release reverse_words.d
 */
import std.algorithm: reverse;
import std.stdio: writeln;
import std.string: find;

void reverse_words(char[] str) {
  // reverse whole string
  reverse(str);

  // reverse each word
  for (auto i = 0; (i = find(str, " ")) != -1; str = str[i + 1..length])
    reverse(str[0..i]);

  // reverse last word
  reverse(str);
}

void main() {
  char[] str = cast(char[])("this is a string");
  writeln(str);
  reverse_words(str);
  writeln(str);
}

Output:

this is a string
string a is this

Answer 12

in Ruby

"this is a string".split.reverse.join(" ")

Answer 13

in C#, in-place, O(n), and tested:

static char[] ReverseAllWords(char[] in_text)
{
    int lindex = 0;
    int rindex = in_text.Length - 1;
    if (rindex > 1)
    {
        //reverse complete phrase
        in_text = ReverseString(in_text, 0, rindex);

        //reverse each word in resultant reversed phrase
        for (rindex = 0; rindex <= in_text.Length; rindex++)
        {
            if (rindex == in_text.Length || in_text[rindex] == ' ')
            {
                in_text = ReverseString(in_text, lindex, rindex - 1);
                lindex = rindex + 1;
            }
        }
    }
    return in_text;
}

static char[] ReverseString(char[] intext, int lindex, int rindex)
{
    char tempc;
    while (lindex < rindex)
    {
        tempc = intext[lindex];
        intext[lindex++] = intext[rindex];
        intext[rindex--] = tempc;
    }
    return intext;
}

Answer 14

Efficient in terms of my time: took under 2 minutes to write in REBOL:

reverse_words: func [s [string!]] [form reverse parse s none]

Try it out: reverse_words "this is a string" "string a is this"

Answer 15

A Ruby solution.

# Reverse all words in string
def reverse_words(string)
  return string if string == ''

  reverse(string, 0, string.size - 1)

  bounds = next_word_bounds(string, 0)

  while bounds.all? { |b| b < string.size }
    reverse(string, bounds[:from], bounds[:to])
    bounds = next_word_bounds(string, bounds[:to] + 1)
  end

  string
end

# Reverse a single word between indices "from" and "to" in "string"
def reverse(s, from, to)
    half = (from - to) / 2 + 1

    half.times do |i|
        s[from], s[to] = s[to], s[from]
        from, to = from.next, to.next
    end

    s
end

# Find the boundaries of the next word starting at index "from"
def next_word_bounds(s, from)
  from = s.index(/\S/, from) || s.size
  to = s.index(/\s/, from + 1) || s.size

  return { from: from, to: to - 1 }
end

Answer 16

Here is my answer. No library calls and no temp data structures.

#include <stdio.h>

void reverse(char* string, int length){
    int i;
    for (i = 0; i < length/2; i++){
        string[length - 1 - i] ^= string[i] ;
        string[i] ^= string[length - 1 - i];
        string[length - 1 - i] ^= string[i];
    }   
}

int main () {
char string[] = "This is a test string";
char *ptr;
int i = 0;
int word = 0;
ptr = (char *)&string;
printf("%s\n", string);
int length=0;
while (*ptr++){
    ++length;
}
reverse(string, length);
printf("%s\n", string);

for (i=0;i<length;i++){
    if(string[i] == ' '){
       reverse(&string[word], i-word);
       word = i+1;
       }
}   
reverse(&string[word], i-word); //for last word             
printf("\n%s\n", string);
return 0;
}