Algorithm – Reverse words in a string

Problem

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.

We want to return a string of the words in reverse order concatenated by a single space.

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.

Discussion

1. Check if the input string s is null or empty. If it is, return an empty string.
2. Trim the input string to remove leading and trailing white space.
3. Create a StringBuilder object named reversedString to store the reversed string.
4. Split the trimmed string s into an array of words using the split(" ") method, which splits the string based on spaces.
5. Iterate over the strArray from the last element to the first (strArray.length - 1 to 0).
6. Inside the loop, check if the current word strArray[i] is not an empty string.
7. If the word is not empty, append it to the reversedString using the append() method.
8. If the current word is not the first word in the reversed order (i.e., i != 0), append a space after the word.
9. After the loop ends, convert the reversedString to a regular string using the toString() method.
10. Return the reversed string as the result of the method.

Time Complexity

1. Splitting the string into an array of words using split(" ") takes O(n) time, where n is the length of the input string.
2. The for loop iterates over the array of words, which takes O(m) time, where m is the number of words in the array.
3. Within the loop, appending words to the reversedString takes O(1) time.
4. Overall, the time complexity of the algorithm is O(n + m), where n is the length of the input string and m is the number of words.

Space Complexity

1. The space complexity of the algorithm is O(n + m), where n is the length of the input string and m is the number of words.
2. The trimmed string s and the array strArray both require O(n) space.
3. The reversedString StringBuilder requires additional space to store the reversed string, which can be up to O(n) in the worst case if all words are present.
4. Therefore, the total space complexity is O(n + m).

Java Solution

public String reverseWords(String s) {
            
            if(s == null || s.length() == 0) return "";
            s = s.trim();

            StringBuilder reversedString = new StringBuilder();
            String[] strArray = s.split(" ");
            for( int i = strArray.length -1; i >= 0; i--){
                if(!strArray[i].equals("")){
                    reversedString.append(strArray[i]);
                    if(i != 0) reversedString.append(" ");
                }
            }
            return reversedString.toString();
        }

Python Solution

def reverseWords(self, s):
        if s is None or len(s) == 0:
            return ""

        s = s.strip()
        reversed_string = []
        str_list = s.split(" ")

        for i in range(len(str_list) - 1, -1, -1):
            if str_list[i] != "":
                reversed_string.append(str_list[i])
    
        return " ".join(reversed_string)

Check out my other article or Algorithm – Roman To Integer here

Our Facebook page is here. You can also find our youtube channel here.