CodingGyan

Reverse the Order of Words

easy Strings

Problem

Read one line. Print the words in reverse order, separated by one space. Extra spaces at the start, at the end and between words are removed.

Constraints

  • 1 <= length <= 10^5, at least one word

Examples

Input

the sky is blue

Output

blue is sky the

Solutions

Best approachTime O(n)Space O(n)

Split the line into words, then read the words from the end. Splitting on one or more spaces removes the extra spaces automatically.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Reverse the word order.
 * Input   : One line of text.
 * Output  : The words in reverse order.
 * Approach: Split into words first.
 * Time    : O(n)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static String solve(String s) {
        // Step 1: Split the text at one or more spaces. trim() removes spaces at both ends first.
        String[] words = s.trim().split("\\s+");

        // Step 2: Walk from the last word to the first word and collect them.
        StringBuilder result = new StringBuilder();
        for (int i = words.length - 1; i >= 0; i--) {
            result.append(words[i]);

            // Step 3: Put one space between words, but not after the last one.
            if (i > 0) {
                result.append(" ");
            }
        }
        return result.toString();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.hasNextLine() ? scanner.nextLine() : "";
        System.out.println(solve(s));
    }
}
Hints (1)
  1. How do you split text on many spaces?

Try these next