Algorithm

Reverse Sentence

Nicholas Wong

Nicholas Wong

— 1 min read
Reverse Sentence

Question

Simple task, reverse words in a sentence.

Solution

In Python, this can be simple because of the build-in functions. We can just split the sentence by spaces, reverse the list, and join them with spaces again.

In C++, this can be complicated. The following might be one of the possible answers. We have to scan from the head to tail, and find the position that a word starts and ends. Then reverse the letters in this word. At the end, reverse all the letters in the whole sentence.

Examples

# function to reverse a sentence 
def reverse_sentence(sentence): 
    return ' '.join(reversed(sentence.split())) 

# main 
print reverse_sentence("I am a student.") 
print reverse_sentence("Testing 1 2 3")

#include <iostream>
using namespace std;

// function to reverse a word, in place 
void reverse_word(string * word, int begin, int end) {
  while (begin < end) {
    char letter = word -> at(begin);
    word -> at(begin) = word -> at(end);
    word -> at(end) = letter;
    begin++;
    end--;
  }
} 

// function to reverse a sentence, in place 
void reverse_sentence(string * sentence) {
  int length = sentence -> size();
  int pointer = 0; // for each character 
  for (int i = 0; i < (int)sentence->size(); i++) { // find word head 
    if (pointer == -1) {
      if (sentence -> at(i) != ' ') pointer = i;
      continue;
    } 
    // find word tail 
    if (sentence -> at(i) == ' ') {
      reverse_word(sentence, pointer, i - 1);
      pointer = -1;
    } 
    // end of string
    if (i == length - 1) {
      reverse_word(sentence, pointer, i - 1);
    }
  } 
  // reverse letters for the whole sentence 
  reverse_word(sentence, 0, sentence -> size() - 1);
} 

// main part 
int main() {
  string text = "I am a student.";
  reverse_sentence( & text);
  cout << text << endl;
}

public class Solution {
  
    private static String reverse_sentence(String sentence) {
        String[] splited = sentence.split(" ");
        StringBuilder builder = new StringBuilder();
        for (int i = splited.length - 1; i >= 0; i--) {
            builder.append(splited[i]);
            if (i > 0) builder.append(" ");
        }
        return builder.toString();
    }
  
    public static void main(String[] args) {
        System.out.println(reverse_sentence("I am a student."));
        System.out.println(reverse_sentence("Testing 1 2 3"));
    }
}

Read more