151. Reverse Words in a String

#string #array

Given an input string s, 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.

Input: s = "    a good   example  "
Output: " example good a "
Explanation: reduce multiple spaces between two words to a single space in the reversed string not containing leading or trailing spaces.

---

Intuition

• split the string on space and add words in the final string from end

Approach

• trim the string to remove any trailing or leading whitespace

• split the string using string.split(" ")

• iterate over the words from the end

• trim the word before appending to final result to ensure we dont add any whitespace

Complexity

Space Complexity	Time Complexity
$\text{O}(n)$	$\text{O}(n)$

• we store the splitted string in an array

• we iterate over the words in the string once

Code

class Solution {
    public String reverseWords(String s) {
        // trim to remove the leading/trailing spaces
        // split on the string to get the individual words
        String[] str = s.trim().split(" ");

        // to store the result
        StringBuilder result = new StringBuilder();

        // iterate over the splitted string in reverse
        for(int i = str.length -1; i >= 0; --i) {

            // spaces can come so trim to ensure we skip them
            if(str[i].trim().isEmpty()) continue;

            result.append(str[i]);

            // only add if not the last word
            if(i > 0) result.append(" ");
        }

        return result.toString();
    }
}