In this article, you will learn to resolve the Reverse Words in a String problem by using Iterative algorithms

Problem

  • Given a string s

  • Write an algorithm to reverse words in s

  • Redundant spaces should be trimmed

Example 1

  • Input: "Hello Koding"

  • Output: "Koding Hello"

Example 2

  • Input: " Live on time, emit no evil "

  • Output: "evil no emit time, on Live"

Approach 1: Splitting and Iterative

  • Split the given string by space character into a words array

  • Iterate the words array in reverse to build the result string

public class ReverseWordsBySplittingAndIterative {  
    static String reverseWords(String s) {
        StringBuilder result = new StringBuilder();

        String[] words = s.split(" ");
        for (int i = words.length - 1; i >= 0; i--) {
            if (!words[i].isEmpty()) {
                result.append(words[i]).append(" ");
            }
        }

        return result.toString().trim();
    }

    public static void main(String[] args) {
        System.out.println(reverseWords("Hello  Koding"));
        System.out.println(reverseWords(" Live on time, emit no evil "));
    }
}
  • Output
Koding Hello  
evil no emit time, on Live

  • Time complexity: O(n) as iterating over an array of size n

  • Space complexity: O(n) as an array of size n is used

Approach 2: Iterative

  • Iterate the words array in reverse to build the result string
    static String reverseWords(String s) {
        StringBuilder result = new StringBuilder();
        int j = s.length();

        for (int i = j-1; i >= 0; i--) {
            char c = s.charAt(i);
            if(Character.isWhitespace(c) || i==0) {
                result.append(s, i, j);
                j = i;
            }
        }

        return result.toString().trim();
    }

    public static void main(String[] args) {
        System.out.println(reverseWords("Hello  Koding"));
        System.out.println(reverseWords(" Live on time, emit no evil "));
    }
}
  • Output
Koding Hello  
evil no emit time, on Live

  • Time complexity: O(n) as iterating over an array of size n

  • Space complexity: O(n) as a string of size n is used

Algorithm