Reverse Words in String Editorial

Practice Problem Link: Reverse Words in String | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a string s, reverse the order of words. A word is a sequence of non-space characters. Words in the string s will have one space between them. There are no leading or trailing spaces.

Approach

The problem can be solved by traversing the string and store all the words in an array of strings in the same sequence. After storing all the words traverse the array from end to start and store all the words in the answer string separated by a space.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(n)

Implementation

C++

string reverseWords(string &s) {
   vector<string> allWords;
   string currentWord = "";
   for(int i = 0; i < s.size(); i++) {
       if(s[i] == ' ') {
           allWords.push_back(currentWord);
           currentWord = "";
       } else {
           currentWord += s[i];
       }
   }
   allWords.push_back(currentWord);
   string ans;
   for(int i = allWords.size() - 1; i > 0; i--) {
       ans += allWords[i];
       ans += ' ';
   }
   ans += allWords[0];
   return ans;
}

Java

class Solution {
   String reverseWords(String s) {
       int numOfWords = 1;
       for (int i = 0; i < s.length(); i++) {
           if(s.charAt(i) == ' ') {
               numOfWords++;
           }
       }
       String[] allWords = new  String[numOfWords];
       String currentWord = "";
       int index = 0;
       for(int i = 0; i < s.length(); i++) {
           if(s.charAt(i) == ' ') {
               allWords[index++] = currentWord;
               currentWord = "";
           } else {
               currentWord += s.charAt(i);
           }
       }
       allWords[index++] = currentWord;
       String ans = "";
       for(int i = index - 1; i > 0; i--) {
           ans += allWords[i];
           ans += ' ';
       }
       ans += allWords[0];
       return ans;
   }
}

Another Approach

This approach has the same time complexity as the previous approach. The idea here is to first reverse the whole string and then again reverse each of the words.

• First, reverse the whole string.
• Assign a pointer to the beginning of the string.
• Traverse the string from i = 0 to i = n - 1 and as soon as space is encountered reverse the string up to that position and then assign the pointer to the next index (i + 1).

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(1)

Implementation

C++

string reverseWords(string &s) {
   int n = s.size();
     for(int i = 0; i < n/2; i++) {
       swap(s[i], s[n - 1 - i]);
   }
   int j = 0;
   for (int i = 0; i < n; i++) {
       if(s[i] == ' ') {
           int start = j, end = i - 1;
           while (j <= (start + end) / 2) {
               swap(s[j], s[end - (j - start)]);
               j++;
           }
           j = i + 1;
       }
   }
   int start = j, end = n - 1;
   while(j <= (start + end) / 2) {
       swap(s[j], s[end - (j - start)]);
       j++;
   }
   return s;
}

Java

class Solution {
   String reverseWords(String s) {
       int n = s.length();
       char[] str = new char[n];
       for (int i = 0; i < n; i++) {
           str[i] = s.charAt(i);
       }
       for(int i = 0; i < n/2; i++) {
           char temp = str[i];
           str[i] = str[n - 1 - i];
           str[n - 1 - i] = temp;
       }
       int j = 0;
       for (int i = 0; i < n; i++) {
           if(str[i] == ' ') {
               int start = j, end = i - 1;
               while (j <= (start + end) / 2) {
                   char temp = str[j];
                   str[j] = str[end - (j - start)];
                   str[end - (j - start)] = temp;
                   j++;
               }
               j = i + 1;
           }
       }
       int start = j, end = n - 1;
       while(j <= (start + end) / 2) {
           char temp = str[j];
           str[j] = str[end - (j - start)];
           str[end - (j - start)] = temp;
           j++;
       }
       s = "";
       for (int i = 0; i < n; i++) {
           s += str[i];
       }
       return s;
   }
}