0%

Leetcode151-reverseWordsInAString

Description

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

Example

Example 1:

1
2
Input: "the sky is blue"
Output: "blue is sky the"

Example 2:
1
2
3
Input: "  hello world!  "
Output: "world! hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:
1
2
3
Input: "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Note:

  • A word is defined as a sequence of non-space characters.
  • Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.
  • You need to reduce multiple spaces between two words to a single space in the reversed string.

Follow up:

For C programmers, try to solve it in-place in O(1) extra space.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public String reverseWords(String s) {
if (s == null || s.length() == 0) return "";
String[] arr = s.trim().split("\\s+");
String res = "";
for (int i = arr.length - 1; i > 0; i--) {
res += arr[i] + " ";
}
res += arr[0];
return res;
}
}

Method 2: Don’t use split/trim

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public class Solution {

public String reverseWords(String s) {
if (s == null) return null;

char[] a = s.toCharArray();
int n = a.length;

// step 1. reverse the whole string
reverse(a, 0, n - 1);
// step 2. reverse each word
reverseWords(a, n);
// step 3. clean up spaces
return cleanSpaces(a, n);
}

void reverseWords(char[] a, int n) {
int i = 0, j = 0;

while (i < n) {
while (i < j || i < n && a[i] == ' ') i++; // skip spaces
while (j < i || j < n && a[j] != ' ') j++; // skip non spaces
reverse(a, i, j - 1); // reverse the word
}
}

// trim leading, trailing and multiple spaces
String cleanSpaces(char[] a, int n) {
int i = 0, j = 0;

while (j < n) {
while (j < n && a[j] == ' ') j++; // skip spaces
while (j < n && a[j] != ' ') a[i++] = a[j++]; // keep non spaces
while (j < n && a[j] == ' ') j++; // skip spaces
if (j < n) a[i++] = ' '; // keep only one space
}

return new String(a).substring(0, i);
}

// reverse a[] from a[i] to a[j]
private void reverse(char[] a, int i, int j) {
while (i < j) {
char t = a[i];
a[i++] = a[j];
a[j--] = t;
}
}
}