Programming Interview Questions 12: Reverse Words in a String

This is probably by far the most common string manipulation interview question. Given an input string, reverse all the words. To clarify, input: “Interviews are awesome!” output: “awesome! are Interviews”. Consider all consecutive non-whitespace characters as individual words. If there are multiple spaces between words reduce them to a single white space. Also remove all leading and trailing whitespaces. So, the output for ”   CS degree”, “CS    degree”, “CS degree   “, or ”   CS   degree   ” are all the same: “degree CS”.

This can be done pretty easily in python since it has very useful functions to do most of the work itself. Split on whitespace (removes multiple contiguous spaces as well as leading and trailing spaces) and reverse the order of words. There are two alternative one-liners:

def reverseWords1(text):
    print " ".join(reversed(text.split()))
 
def reverseWords2(text):
    print " ".join(text.split()[::-1])

But this kind of seems like cheating since python is doing most of the heavy work for us. Let’s do more work by looping over the text and extracting the words ourselves instead of using the function split. We push the words to a stack and in the end pop all to reverse. Here is the code:

def reverseWords3(text):
    words=[]
    length=len(text)
    space=set(string.whitespace)
    index=0
    while index<length:
        if text[index] not in space:
            wordStart=index
            while index<length and text[index] not in space:
                index+=1
            words.append(text[wordStart:index])
        index+=1
 
    print " ".join(reversed(words))

All these solutions use extra space (stack or constructing a new list), but we can in fact solve it in-place. Reverse all the characters in the string, then reverse the letters of each individual word. This can be done in-place using C or C++. But since python strings are immutable we can’t modify them in-place, any modification to a string returns a new string. Here’s the python code which uses the same logic but not in-place:

def reverseWords4(text):
    words=text[::-1].split()
    print " ".join([word[::-1] for word in words])

In C/C++ we would first reverse the entire string and loop over it with two pointers, read and write. We’ll overwrite the string in-place. The resulting string may be shorter than the original one, because we have to remove multiple consecutive spaces as well as leading and trailing ones, that’s why we need 2 pointers. But note that write pointer can never pass read pointer so there won’t be any conflicts. Here is the C code:

void reverseWords(char *text)
{
    int length=strlen(text);
    reverseString(text, 0, length-1, 0);
    int read=0, write=0;
    while (read<length)
    {
        if (text[read]!=' ')
        {
            int wordStart=read;
            for ( ;read<length && text[read]!=' '; read++);
            reverseString(text, wordStart, read-1, write);
            write+=read-wordStart;
            text[write++]=' ';
        }
        read++;
    }
    text[write-1]='\0';
}
 
void reverseString(char *text, int start, int end, int destination)
{
    // reverse the string and copy it to destination
    int length=end-start+1;
    int i;
    memcpy(&text[destination], &text[start], length*sizeof(char));
    for (i=0; i<length/2; i++)
    {
        swap(&text[destination+i], &text[destination+length-1-i]);
    } 
}

This is one of the most common interview questions, so anyone preparing for interviews should be able to solve it hands down.

VN:F [1.9.22_1171]
Rating: 10.0/10 (10 votes cast)
Programming Interview Questions 12: Reverse Words in a String, 10.0 out of 10 based on 10 ratings

This entry was posted in Programming Interview. Bookmark the permalink.
  • Anonymous

    it’s so cool, it’s what i’m looking for. thanks for sharing.

  • ys

    I think it having complexity of O(n^2) [n-square] cannot we do more better for this problem?

    • aduyng

      No, it is not O(n^2), I think it is O(n) because you are just doing one scan thru all characters. Here is my solution in javascript.

      • wynnej1983

        i think its O(2n) ~ O(n)

  • Alexander Sharma

    Hi

    I wanted to share this solution in java.

    import java.util.*;
    public class Rev {
    public static void ReverseWords (char str[])
    {
    int start = 0, end = 0, length;
    length = str.length;
    /* Reverse entire string */
    ReverseString(str, start, length – 1);
    while (end < length) {
    if (str[end] != ' ') { /* Skip non-word characters */
    /* Save position of beginning of word */
    start = end;
    /* Scan to next non-word character */
    while (end start) {
    /* Exchange characters */
    temp = str [start];
    str [start] = str [end] ;
    str [end] = temp;
    /* Move indices towards middle */
    start++; end–;
    }
    return;
    }
    public static void main(String[] args){
    String s = “Hello World”;
    char[] str = s.toCharArray();
    ReverseWords(str);
    String output = “”;
    for(int i = 0; i < str.length; i++)
    output+=str[i];
    System.out.println(output);
    }
    }
    output: World Hello

  • Dejun Zhou

    You don’t need to do memory copy if start == destination

  • manish

    hi
    try this
    this is the solution of program converting the string eg. from “manish is cool” to “cool is manish”

    main()
    {
    char s[111];
    char s1[111][111];
    int i=0,j=0,k=0,l=0;
    printf(“enter the to words string:->”);
    gets(s);
    while(s[i]!=0)
    {
    i++;
    if(s[i]==’ ‘)
    l++;
    }
    l++;
    printf(“string after reversing its secquence of word\n”);
    printf(“______________________________________________\n”);
    i=0;
    for(k=0;k=0;i–)
    printf(“%s “,s1[i]);
    getch();
    }

    • manish

      uper one was misprint
      try this
      main()
      {
      char s[111];
      char s1[111][111];
      int i=0,j=0,k=0,l=0;
      printf(“enter the to words string:->”);
      gets(s);
      while(s[i]!=0)
      {
      i++;
      if(s[i]==’ ‘)
      l++;
      }
      l++;

      printf(“string after reversing its secquence of word\n”);
      printf(“______________________________________________\n”);
      i=0;
      for(k=0;k=0;i–)
      printf(“%s “,s1[i]);

      getch();
      }

      • manish

        ther is sum problem in this site

  • Ravi

    @Manish: can u plz upload the solution and share the link if possible…

  • Ravi

    @Manish: can u plz upload the solution and share the link if possible…,,,,

  • Rohit Pal

    char* reversedString(char* Sentence) {

    int length = strlen(Sentence);
    char *result = new char[length];
    int startPtr = 0;
    int POS = 0;

    for (int i = 0; i = startPtr; j–)
    result[POS++] = Sentence[j];
    result[POS++] = ‘ ‘;
    startPtr = POS;
    }

    else if(i == length -1) {
    for (int j = i; j >= startPtr; j–)
    result[POS++] = Sentence[j];
    }

    return result;
    }

  • Fatih

    Here is the C# version (I think pointers should be used to make in in-place but I am not good at using pointers in C#)

    public void reverseTheSentence(String sentence)

    {

    sentence = reverseAllLettersInAString(sentence);

    string[] words = sentence.Split(new char[1]{‘ ‘});

    for (int i = 0; i < words.Length; i++)

    {

    string word = words[i];

    if(String.IsNullOrWhiteSpace(word)){

    continue;

    }

    Console.Write(reverseAllLettersInAString(word));

    if (i != words.Length – 1)

    {

    Console.Write(" ");

    }

    }

    }

    private string reverseAllLettersInAString(string s)

    {

    char[] sentenceCharArray = s.ToCharArray();

    for (int i = 0; i < sentenceCharArray.Length / 2; i++)

    {

    char firstChar = sentenceCharArray[i];

    sentenceCharArray[i] = sentenceCharArray[sentenceCharArray.Length - i - 1];

    sentenceCharArray[sentenceCharArray.Length - i - 1] = firstChar;

    }

    return new String(sentenceCharArray);

    }

  • Skamy

    I came across this post. You have a great site. I do have a comment about the C/C++ implementation. I feel like if the input for reverseWords is a 0 length string, then “text[write-1] = ”;” will try to write to invalid memory. If the input string only has spaces then the same problem will happen and additionally the string wont shrink the spaces. Do I observe it right?

  • Ankit Kapadia

    One more approach to this problem mentioned in “Programming Interviews Exposed” book is: Traverse the string from backward. When you encounter space go forward until space or end of string simultaneously adding chars into result buffer.

  • Guest

    Here is the code in C++ which is working fine in test cases given above :
    please let me knw if there is a mistake !!

    #include
    #include
    using namespace std;
    int main(){
    int i,j,flag,flag2;
    string str1,str2;
    getline(cin,str1);
    int len=str1.size();
    flag2=len;
    for(i=len-1;i>=-1;i–)
    {
    if(str1[i]==’ ‘ || i==-1)
    {
    flag=i;
    for(j=flag+1;j<flag2;j++)
    str2+=str1[j];
    str2=str2+' ';
    flag2=i;
    }
    }
    cout<<"n Reverse String:"<<str2;
    return 0;
    }

  • Shubham Gupta

    Here is the code in C++ which is working fine in test cases given above:
    let me knw if there is some mistake :

    http://ideone.com/Dak8Wp