Question

Formatted question description: https://leetcode.ca/all/151.html

151	Reverse Words in a String

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

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

Update (2015-02-12):
For C programmers: Try to solve it in-place in O(1) space.

click to show clarification.

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.

@tag-string

Algorithm

First flip the entire string once, and then flip each word separately (or flip each word separately, and then flip the entire string once).

If we use Java’s String split function to do it, it is very simple, there are not so many moths, simple and clear.

  • we first call the original string to trim() to remove redundant spaces,
  • and then call split() to separate , The delimiter is set to “\s+”, this is actually a regular expression, \s means space character, + means there can be one or more space characters,
  • then we can separate the words into one character in the string array, then we start from the end, take out the words one by one and add them to the result res, and add space characters between the words.
    • Note that we leave the first word, and then add it when returning.

Code

Java

public class Reverse_Words_in_a_String {

    // basically, 1st scan to reverse whole string including space,
    // 2nd scan to reverse each word when encountering a space
    public class Solution_2Scan {
        public String reverseWords(String s) {

            if (s == null || s.length() == 0) {
                return s;
            }

            int storeIndex = 0, n = s.length();
            StringBuilder sb = new StringBuilder(s).reverse();
            for (int i = 0; i < n; ++i) {
                if (sb.charAt(i) != ' ') {
                    if (storeIndex != 0) sb.setCharAt(storeIndex++, ' ');
                    int j = i;
                    while (j < n && sb.charAt(j) != ' ') sb.setCharAt(storeIndex++, sb.charAt(j++));
                    String t = new StringBuilder(sb.substring(storeIndex - (j - i), storeIndex)).reverse().toString();
                    sb.replace(storeIndex - (j - i), storeIndex, t);
                    i = j;
                }
                // else, skip space
            }
            sb.setLength(storeIndex);
            return sb.toString();

        }
    }

    public class Solution_sb {
        public String reverseWords(String s) {
            String res = "";
            String[] words = s.trim().split("\\s+");
            for (int i = words.length - 1; i > 0; --i) {
                res += words[i] + " ";
            }
            return res + words[0];
        }
    }

    public class Solution {
        public String reverseWords(String s) {

            if (s == null || s.length() == 0) {
                return s;
            }

            String res = "";
            String[] words = s.trim().split("\\s+");
            for (int i = words.length - 1; i > 0; --i) {
                res += words[i] + " ";
            }
            return res + words[0];
        }
    }

}

All Problems

All Solutions