Reverse Words in a String

Given an input string s, reverse the order of the words. A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Example 1:

Input: s = "the sky is blue"
Output: "blue is sky the"

Example 2:

Input: s = "  hello world  "
Output: "world hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

Input: s = "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Example 4:

Input: s = "  Bob    Loves  Alice   "
Output: "Alice Loves Bob"

Example 5:

Input: s = "Alice does not even like bob"
Output: "bob like even not does Alice"

Constraints:

  • 1 <= s.length <= 104
  • s contains English letters (upper-case and lower-case), digits, and spaces ' '.
  • There is at least one word in s.

Note:

  • A word is defined as a sequence of non-space characters.
  • The input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.
  • You need to reduce multiple spaces between two words to a single space in the reversed string.

Here we consider two different solutions of linear time and space complexity:

  1. Use built-in split and reverse. Benefits: in-place and the simplest one to write.
  2. Two passes approach with a Stack. Move along the string, word by word, and push each new word in a Stack. Convert the Stack back into a string. 

Approach 1: Built-in Split + Reverse:

public String reverseWords(String s) {
    // remove leading spaces
    s = s.trim();
    // split by multiple spaces
    List<String> wordList = Arrays.asList(s.split("\\s+"));
    Collections.reverse(wordList);
    return String.join(" ", wordList);
}

Complexity Analysis

  • Time complexity: O(N), where N is a number of characters in the input string.
  • Space complexity: O(N), to store the result of the split by spaces.

Approach 2: Stack of Words:

public String reverseWords(String s) {
    int left = 0;
    int right = s.length() - 1;

    // remove leading spaces
    while (left <= right) {
        if (s.charAt(left) == ' ') {
            left++;
        } else break;
    }

    // remove trailing spaces
    while (left <= right) {
        if (s.charAt(right) == ' ') {
            right--;
        } else break;
    }

    StringBuilder word = new StringBuilder();
    Stack<String> wordStack = new Stack<>();
    while (left <= right) {
        char current = s.charAt(left);
        if (current != ' ') {
            word.append(current);
        } else {
            if (word.length() > 0) {
                String sWord = word.toString();
                wordStack.push(sWord);
                word = new StringBuilder();
            }
        }
        left++;
    }
    if (word.length() > 0) {
        String sWord = word.toString();
        wordStack.push(sWord);
    }
    StringBuilder result = new StringBuilder();
    while (wordStack.size() > 0) {
        result.append(wordStack.pop());
        if (wordStack.size() != 0) result.append(" ");
    }
    return result.toString();
}

Complexity Analysis

  • Time complexity: O(N), where N is a number of characters in the input string.
  • Space complexity: O(N), to store the result of the split by spaces.

Categories: String

Tagged as: ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s