LeetCode151. Reverse Words in a String

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

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.


reverse

lc in cpp

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
string reverseWords(string s) {
int first = 0, index = 0;
reverse(s.begin(), s.end());
for (;first < s.size();first++)
{
if (s[first] != ' ')
{
//当前记录的位置如果不是0,前面就加空格
if (index != 0) s[index++] = ' ';

//end开始走
int end = first;
//当目前end不为空时,这个单词还没结束,更新index
while (end<s.size()&&s[end] != ' ')
s[index++] = s[end++];

//翻转单词
reverse(s.begin() + index - (end - first),
s.begin() + index);
first = end;
}
}
s.resize(index);
return s;
}
  1. 因为去掉重复空格,所以新字符串的长度跟原来的不一样,所以用index记录当前字符串的长度,并且随时更新.
  2. 先翻转整个string.
  3. 设置一个first指针,指向单词的第一个字母,如果遇到空格就跳过.
    1. 更新s[index++],如果当前单词不是第一个单词,前面就要加空格.
    2. end指针从first处开始走,来记录单词的最后一个字母,如果end没到顶,并且end不为空,更新s[index++].
    3. 翻转这个单词,开始的索引是s.begin()+index-(end-first),结束于s.begin()+index.
    4. 最后将first移到最新的index处,进行新一轮的翻转单词.
  4. 最后重新分配字符串的大小,reseize(index).这个index在前面已经++过了,所以就是长度.

my code in cpp

开始没有想到去掉重复空格的方法.

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
string reverseWords(string s) {
int l = -1, r = -1;
while (r<(int)s.size())//size是unsigned int,强转int
{
//单词首字母
while (++r<s.size()&&s[r] == ' ') ;
int left = r;

//单词尾字母
while (++r < s.length() && s[r] != ' ') ;
r--;

//翻转单词
int right = r;
while (left < right) swap(s[left++], s[right--]);
}

//翻转string
l = 0, r = s.length() - 1;
while (l < r) swap(s[l++], s[r--]);

//去首尾
s.erase(0, s.find_first_not_of(" "));
s.erase(s.find_last_not_of(" ") + 1);
return s;
}

stringstream

  1. 把字符串s装载入字符串流 is 中.
  2. 把第一个单词赋给s.
  3. 定义一个临时变量字符串tmp.将is的单词赋给tmp.并且通过’ ‘把tmp连到s的前面.
    1. 如果is含有非空格字符,每次>>操作就会提取连在一起的非空格字符.
    2. 如果is为空,那么就不会进入while循环;
    3. 如果is为许多空格字符连在一起,那么第一个>>操作就会提取出这些空格字符放入s中,然后不进入while循环,这时候我们只要判断一下s的首字符是否为空格字符,是的话就将s清空即可.

lc in cpp

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

getline

  1. 也是使用stringstream来做,使用了getline.
  2. 第三个参数是设定分隔字符,我们用空格字符来分隔,这个跟上面的>>操作是有不同的,每次只能过一个空格字符,如果有多个空格字符连在一起,那么t会赋值为空字符串.
  3. 在处理t的时候首先要判断其是否为空,是的话直接跳过.

lc in cpp2

1
2
3
4
5
6
7
8
9
10
string reverseWords(string s) {
istringstream is(s);
s = "";
string t = "";
while (getline(is, t, ' ')) {
if (t.empty()) continue;
s = (s.empty() ? t : (t + " " + s));
}
return s;
}

1


JAVA

  1. 调用trim()来去除冗余空格.
  2. 调用split()来分隔,分隔符设为”\s+”,这其实是一个正则表达式,\s表示空格字符,+表示可以有一个或多个空格字符,那么我们就可以把单词分隔开装入一个字符串数组中.
  3. 从末尾开始,一个个把单词取出来加入结果res中,并且单词之间加上空格字符,注意我们把第一个单词留着不取,然后返回的时候再加上即可.
1
2
3
4
5
6
7
8
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];
}

JAVA 2

  1. 这里的分隔符没有用正则表达式,而是直接放了个空格符进去,后面还是有+号,跟上面的写法得到的效果是一样的.
  2. 对字符串数组进行翻转
  3. 调用join()函数来把字符串数组拼接成一个字符串,中间夹上空格符即可
1
2
3
4
5
public String reverseWords(String s) {
String[] words = s.trim().split(" +");
Collections.reverse(Arrays.asList(words));
return String.join(" ", words);
}
Thanks for Support.