151. Reverse Words in a String

Hello, reader 👋🏽 ! Welcome to day 43 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.

Today, I will be picking up LeetCode's daily challenge problem: 151. Reverse Words in a String.

🤔 Problem Statement

• Given an input string s, reverse the order of the words.
• Return a string of the words in reverse order concatenated by a single space.
• The string 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 and not include any extra spaces.
• E.g.:
  • s = "the sky is blue" => "blue is sky the"
  • s = " hello world " => "world hello"

💬 Thought Process - Two Pointers

• Since strings in Java are immutable we will have to use extra space to reverse the string.
• We keep traversing the string s until we find the first non-space character from left to right at index i.
• When we find the first non-space character, we then traverse until we find a non-space character at index j.
• This range of characters from s[i] to s[j-1] represents a word.
• Every time we find a word, we add the word to the 0th index (Since the word needs to be reversed. This ensures the first last word is added in the beginning).
• We will also append a space if the resultant word is not empty (that means we found the first word which is supposed to be the last word in the reversed string).

👩🏽‍💻 Solution - Two Pointers

• Below is the code for the two pointers approach.

class Solution {
    public String reverseWords(String s) {
        int n = s.length();
        StringBuilder sb = new StringBuilder();
        int i = 0;
        while(i < n) {
            char ch = s.charAt(i);
            if(ch == ' ') {
                i++;
                continue;
            }

            int j = i;
            StringBuilder word = new StringBuilder();
            while(j < n && s.charAt(j) != ' ') {
                word.append(s.charAt(j));
                j++;
            }
            if(!sb.isEmpty()) word.append(" ");
            i = j;
            sb.insert(0, word);
        }


        return sb.toString();
    }
}

Time Complexity: O(n * m)
    - n = length of string
    - m = length of the longest word
Space Complexity: O(k * m)
    - m = length of the longest word
    - k = number of words
        - We are using additional space to store every individual word in the string.

• We can also do the above approach in the opposite way. That is, instead of traversing the string from left to right, we will traverse the string from right to left and build the word and keep appending this word to the result.

class Solution {
    public String reverseWords(String s) {
        int n = s.length();
        StringBuilder sb = new StringBuilder();
        int i = n-1;
        int firstWordBegins = 0;
        // We need this because we need the index of the first 
        // word in the input string
        // This will help us to know if we need to include a space
        // after we find each word or not
        while(firstWordBegins < n && s.charAt(firstWordBegins) == ' ') {
            firstWordBegins++;
        }

        while(i >= 0) {
            char ch = s.charAt(i);
            if(ch == ' ') {
                i--;
                continue;
            }

            int j = i;
            StringBuilder word = new StringBuilder();
            while(j >= 0 && s.charAt(j) != ' ') {
                j--;
            }
            int k = j+1;
            while(k <= i) {
                word.append(s.charAt(k));
                k++;
            }

            // Don't add space after the last word in reversed string
            if(j+1 != firstWordBegins) word.append(" ");
            sb.append(word);

            i = j;
        }

        return sb.toString();
    }
}

You can find the link to the GitHub repo for this question here: 151. Reverse Words in a String.

Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!