[LeetCode 151] Reverse Words in a String

Question

Given an input string, reverse the string word by word.

For example,
Given s = "the sky is blue",
return "blue is sky the".

Clarification:

What constitutes a word?
A sequence of non-space characters constitutes a word.
Could the input string contain leading or trailing spaces?
Yes. However, your reversed string should not contain leading or trailing spaces.
How about multiple spaces between two words?
Reduce them to a single space in the reversed string.

Stats

Adjusted Difficulty	3
Time to use	--------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is an very classic question, and there is a very nice solution.

Solution

First solution is read each character from the back, and insert each word into answer String. I used this method, and passed in 2 attempts. I have always been afriad of string question, and this time it gave me an easy time.

I post my code below. Altough it can be better if I use StringBuilder. Most blog/forum would give this solution including this one.

However, previous solution uses extra space. We can do it in-place suggested by this post.

Reverse the entire string, then reverse the letters of each individual word.

After the first pass the string will be
s1 = "Z Y X si eman yM"
    
and after the second pass it will be
s1 = "Z Y X is name My"
    

There are 2 things to note.

One, the edge cases are easily omitted, like all-space input, double-space in between, and a lot more.

Two, The Clarification part is extremely helpful for writing a bug-free solution. It’s always better to clarify further about what the question is ask. For example, can we use String.split() and String.substring()? (normally we would better not to) Can we use any extra space? That decides weather we copy by substring or by character.

In conclusion, this is an easy question that’s not easy to get correct answer. Practise more! And since this is the last post of Leetcode questions, my focus from tomorrow onwards will be shifted to “CC150”. Thanks for reading!

Code

My code. pointer solution.

public String reverseWords(String s) {
    if (s.length() == 0) return "";
    int p = s.length() - 1;
    // p points to the last non-space character
    String ans = "";
    while (p >= 0) {
        int j = p;
        while (j >= 0 && s.charAt(j) != ' ') {
            j --;
        }
        ans += s.substring(j + 1, p + 1) + " ";
        p = j;
        while (p >= 0 && s.charAt(p) == ' ') {
            p--;
        }
    }
    return ans.trim();
}

Updated on Sep 12th: updated with 3-step-reverse method.

public String reverseWords(String s) {
    if (s == null || s.length() == 0) {
        return s;
    }
    StringBuilder ans = new StringBuilder();
    int len = s.length();
    int p = len - 1;
    while (p >= 0) {
        while (p >= 0 && s.charAt(p) == ' ') {
            p--;
        }
        if (p == -1) {
            break;
        }
        StringBuilder word = new StringBuilder();
        while (p >= 0 && s.charAt(p) != ' ') {
            word.append(s.charAt(p));
            p--;
        }
        if (ans.length() == 0) {
            ans.append(word.reverse().toString());
        } else {
            ans.append(" " + word.reverse().toString());
        }
    }
    return ans.toString();
}

Woodstock Blog

a tech blog for general algorithmic interview questions