Reverse Words in a String

Problem Statement

Given a sentence of the form of words separated by spaces, return a new sentence that consists of the words of the original sentence in the reverse order.

Sample Test Cases

Input 1:

s = “Hello World”

Output 1:

World Hello

Input 2:

s = “This is a good day”

Output 2:

day good a is This

Approach

Naive Approach

The naive approach for this problem is to split the string into individual words using the spaces as delimiters, and then print the words in reverse order.

Code / Implementation:

C++ Code

string reverseStringByWords(string s) {
  vector < string > words;
  string word = "";
  for (char c: s) {
    if (c == ' ') {
      words.push_back(word);
      word = "";
    } else {
      word += c;
    }
  }
  words.push_back(word);
  string ans = "";
  reverse(words.begin(), words.end());
  for (auto x: words) {
    ans += x;
    ans += " ";
  }
  return ans;
}

Java Code

public static void reverse(char[] ch, int left, int right) {
  while (left <= right) {
    char temp = ch[right];
    ch[right] = ch[left];
    ch[left] = temp;
    left++;
    right--;
  }
}
public static String reverseByWords(String s) {
  char[] ch = s.toCharArray();
  int beg = 0;
  for (int i = 0; i < ch.length; i++) {
    if (ch[i] == ' ') {
      reverse(ch, beg, i);
      beg = i + 1;
    }
  }
  reverse(ch, beg, ch.length - 1);
  reverse(ch, 0, ch.length - 1);
  String ans = Arrays.toString(ch);
  return ans;
}

Python Code

def reverse(s, left, right):
    while left <= right:
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1


def reverseByWords(s):
    s = list(s)
    n = len(s)
    beg = 0
    for i in range(n):
        if s[i] == " ":
            reverse(s, beg, i - 1)
            beg = i + 1
    reverse(s, beg, n - 1)
    reverse(s, 0, n - 1)
    s = "".join(s)
    return s

Complexity Analysis:

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

Optimal Approach

The optimal approach tries to swap the words of the string from the beginning and end, using a two-pointers-based approach, to reverse the string in constant space. The algorithm is as follows:

• Convert the string into an array of strings, which will store the words.
• Initialize the 2 pointers left and right to 0 and string.length() – 1 respectively.
• While the left pointer does not exceed the right pointer, swap the elements at the left and right pointer, move the left pointer forward and the right pointer backward by 1 place.
• Finally, return the final calculated string.

Implementation:

C++ Code

string reverseByWords(string s) {
  vector < string > words;
  string str = "";
  for (char c: s) {
    if (c == ' ') {
      words.push_back(str);
      str = "";
    } else {
      str += c;
    }
  }
  words.push_back(str);
  int left = 0, right = words.size() - 1;
  while (left <= right) {
    swap(words[left], words[right]);
    left++;
    right--;
  }
  string ans = "";
  for (auto x: words) {
    ans += x;
    ans += " ";
  }
  ans.pop_back();
  return ans;
}

Java Code

public static String reverseByWords(String s) {
  String[] words = s.split("\\s");
  int left = 0, right = words.length - 1;
  while (left <= right) {
    String temp = words[left];
    words[left] = words[right];
    words[right] = temp;
    left += 1;
    right -= 1;
  }
  String ans = String.join(" ", words);
  return ans;
}

Python Code

def reverseByWords(s):
    s = s.split(" ")
    left = 0
    right = len(s) - 1
    while left <= right:
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1
    s = " ".join(s)
    return s

Complexity Analysis:

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

Practice Problem:

Reverse the String

FAQs

1. When a problem is asked to be solved in constant space, what should be the thought process?

A. While the idea may vary from problem to problem, swapping is a very common method used in problems requiring to be solved in constant space.

2. What is the time complexity of the swap function in C++?

A. The swap function in C++ works in O(1) time complexity.