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.

链接： http://leetcode.com/problems/reverse-words-in-a-string/

6/13/2017

8ms, 64%

高亮部分是需要记住的Java String方法，reverse(char[], int start, int end)中start, end是左开右闭。

 1 public class Solution {
 2     public String reverseWords(String s) {
 3         if (s == null || s.equals("")) {
 4             return s;
 5         }
 6         char[] characters = s.toCharArray();
 7         int validLength = 0;
 8         for (int i = 0; i < s.length(); i++) {
 9             if (characters[i] != ' ' || i != 0 && characters[i - 1] != ' ') {
10                 characters[validLength] = characters[i];
11                 validLength++;
12             }
13         }
14         if (validLength == 0) {
15             return "";
16         }
17         if (characters[validLength - 1] == ' ') {
18             validLength -= 1;
19         }
20 
21         char[] trimmedChars = new char[validLength];
22         for (int i = 0; i < validLength; i++) {
23             trimmedChars[i] = characters[i];
24         }
25         reverse(trimmedChars, 0, validLength);
26         int startIndex = 0;
27         for (int i = 1; i <= validLength; i++) {
28             if (i == validLength || trimmedChars[i] == ' ') {
29                 reverse(trimmedChars, startIndex, i);
30                 startIndex = i + 1;
31             }
32         }
33         return String.copyValueOf(trimmedChars);
34     }
35     private void reverse(char[] chars, int start, int end) {
36         for (int i = start, j = end - 1; i <= j; i++, j--) {
37             char tmp = chars[i];
38             chars[i] = chars[j];
39             chars[j] = tmp;
40         }
41         return;
42     }
43 }

还可以用string直接来操作，留给二刷或者其他题目。

别人用trim(), split()的方法，原来多个whitespace是用split(" +")作为regex来表示的

https://discuss.leetcode.com/topic/11785/java-3-line-builtin-solution

1 public String reverseWords(String s) {
2     String[] words = s.trim().split(" +");
3     Collections.reverse(Arrays.asList(words));
4     return String.join(" ", words);
5 }