151. Reverse Words in a String

  • 15.7%

https://leetcode.com/problems/reverse-words-in-a-string/

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

1
2
3
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.

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.


方法一:

我的代码实现:

Oct 17, 2017

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
void reverseWords(string &s) {
if(s.empty()) return;
reverse(s.begin(), s.end());
int start = 0;
int i = 0;
for(; i<s.size(); i++){
if(s[i]!=' '){
if(start!=0) s[start++] = ' ';
int j = i;
while(j<s.size() && s[j]!=' ') s[start++] = s[j++];
reverse(s.begin()+start-(j-i), s.begin()+start);
i = j;
}
}
// s.erase(s.begin()+start) 只会删除指定点的字符
s.erase(s.begin()+start, s.end());
return;
}
};

9ms, 28.03%, October 14, 2016

https://discuss.leetcode.com/topic/3298/in-place-simple-solution

First, reverse the whole string, then reverse each word.

有疑问,为何最后使用erase,同时中间为何s[storeIndex++]=s[j++]?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
void reverseWords(string &s) {
reverse(s.begin(), s.end());
int storeIndex = 0;
for(int i=0; i<s.size(); i++){
if(s[i] != ' '){
if(storeIndex!=0) s[storeIndex++] = ' ';
int j = i;
while(j < s.size() && s[j] != ' ') s[storeIndex++] = s[j++];
reverse(s.begin()+storeIndex-(j-i), s.begin()+storeIndex);
i = j;
}
}
s.erase(s.begin()+storeIndex, s.end());
}
};

https://discuss.leetcode.com/topic/5319/c-solution-in-place-runtime-o-n-memory-o-1

The idea is to ignore the extra spaces, reverse words one by one and reverse the whole string in the end.
I think for the interview it is good to show that substr or istringstream can be used too.
The idea is taken from here

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
class Solution {
public:

// function to reverse any part of string from i to j (just one word or entire string)
void reverseword(string &s, int i, int j){
while(i<j){
char t=s[i];
s[i++]=s[j];
s[j--]=t;
}
}

void reverseWords(string &s) {

int i=0, j=0;
int l=0;
int len=s.length();
int wordcount=0;

while(true){
while(i<len && s[i] == ' ') i++; // skip spaces in front of the word
if(i==len) break;
if(wordcount) s[j++]=' ';
l=j;
while(i<len && s[i] != ' ') {s[j]=s[i]; j++; i++;}
reverseword(s,l,j-1); // reverse word in place
wordcount++;

}

s.resize(j); // resize result string
reverseword(s,0,j-1); // reverse whole string
}
};

https://discuss.leetcode.com/topic/3087/accepted-simple-cpp-code-in-just-a-few-lines

Accepted simple cpp code in just a few lines

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
void reverseWords(string &s) {
string result;
int pos = 0;
for (int i = 0; i < s.size(); i ++){
if (s[i] == ' '){
if (i > pos )
result = s.substr(pos,i-pos)+ " " + result ;
pos = i + 1;
}
else if (i == s.size()-1)
result = s.substr(pos,s.size()-pos)+" "+result;
}
s = result.substr(0,result.size()-1) ;
}
};

https://discuss.leetcode.com/topic/10199/5-lines-c-using-stringstream

5 lines C++ using

1
2
3
4
5
6
7
void reverseWords(string &s) {
istringstream is(s);
string tmp;
is >> s;
while(is >> tmp) s = tmp + " " + s;
if(s[0] == ' ') s = "";
}

java

https://discuss.leetcode.com/topic/2742/my-accepted-java-solution

I’m splitting on the regex for one-or-more whitespace, this takes care of multiple spaces/tabs/newlines/etc in the input. Since the input could have leading/trailing whitespace, which would result in empty matches, I first trim the input string.

Now there could be three possibilities:

  1. The input is empty: “”, parts will contain [“”]. The for loop is skipped and “” + “” is returned.
  2. The input contains only one part: “a”, parts will contain [“a”]. The for loop is skipped and “” + “a” is returned.
  3. The input contains multiple parts: “a b c”, reverse the order of all but the first part: “c b “ in the for loop and return “c b “ + “a”.

Obviously this is not the fastest or most memory efficient way to solve the problem, but optimizations should only be done when they are needed. Readable code is usually more important than efficient code.

How to make it efficient?

  1. Use a StringBuilder to concatenate the string parts, instead of concatenating strings directly. This will (I assume) build something like a linked-list of string parts, and only allocate the new string when you need it, instead of on each concatenation.
  2. Iterate over the string, instead of using trim/split. Store the index of the last character in the word, when you find the first character, copy the substring to the output string.
  3. Instead of using substring, insert the word-characters directly in the StringBuilder. Assuming they’re using a linked-list or tree, this could be a whole last faster.
1
2
3
4
5
6
7
8
9
10
public class Solution {
public String reverseWords(String s) {
String[] parts = s.trim().split("\\s+");
String out = "";
for (int i = parts.length - 1; i > 0; i--) {
out += parts[i] + " ";
}
return out + parts[0];
}
}

https://discuss.leetcode.com/topic/18189/clean-java-two-pointers-solution-no-trim-no-split-no-stringbuilder

Clean Java two-pointers solution (no trim( ), no split( ), no StringBuilder)

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
50
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;
}
}

}

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

Java 3-line builtin solution

1
2
3
4
5
public String reverseWords(String s) {
String[] words = s.trim().split(" +");
Collections.reverse(Arrays.asList(words));
return String.join(" ", words);
}
谢谢你,可爱的朋友。