151. Reverse Words in a String (Medium)
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.
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.
Solution 1: 9ms
这道题让我们翻转字符串中的单词,题目中给了我们写特别说明,如果单词之间遇到多个空格,只能返回一个,而且首尾不能有单词,并且对C语言程序员要求空间复杂度为O(1),所以我们只能对原字符串s之间做修改,而不能声明新的字符串。那么我们如何翻转字符串中的单词呢,我们的做法是,先整个字符串整体翻转一次,然后再分别翻转每一个单词(或者先分别翻转每一个单词,然后再整个字符串整体翻转一次),此时就能得到我们需要的结果了。那么这里我们需要定义一些变量来辅助我们解题,storeIndex表示当前存储到的位置,n为字符串的长度。我们先给整个字符串反转一下,然后我们开始循环,遇到空格直接跳过,如果是非空格字符,我们此时看storeIndex是否为0,为0的话表示第一个单词,不用增加空格;如果不为0,说明不是第一个单词,需要在单词中间加一个空格,然后我们要找到下一个单词的结束位置我们用一个while循环来找下一个为空格的位置,在此过程中继续覆盖原字符串,找到结束位置了,下面就来翻转这个单词,然后更新i为结尾位置,最后遍历结束,我们剪裁原字符串到storeIndex位置,就可以得到我们需要的结果,代码如下:
class Solution {
public:
void reverseWords(string &s) {
int n = s.size(), idx = 0;
reverse(s.begin(), s.end());
for (int i = 0; i < n; ++i) {
if (s[i] != ' ') {
if (idx != 0) s[idx++] = ' ';
int j = i;
while (i < n && s[i] != ' ') s[idx++] = s[i++];
reverse(s.begin()+idx-(i-j), s.begin()+idx);
// cout << s << endl;
}
}
s.resize(idx);
}
};
Solution 2: istringstream
version 1: 9ms 下面我们来看使用字符串流类stringstream的解法,我们先把字符串装载入字符串流中,然后定义一个临时变量tmp,然后把第一个单词赋给s,这里需要注意的是,如果含有非空格字符,那么每次>>操作就会提取连在一起的非空格字符,那么我们每次将其加在s前面即可;如果原字符串为空,那么就不会进入while循环;如果原字符串为许多空格字符连在一起,那么第一个>>操作就会提取出这些空格字符放入s中,然后不进入while循环,这时候我们只要判断一下s的首字符是否为空格字符,是的话就将s清空即可,参见代码如下:
class Solution {
public:
void reverseWords(string &s) {
istringstream is(s);
string tmp;
is >> s;
while (is >> tmp) s = tmp + ' ' + s;
if (!s.empty() && s[0] == ' ') s = "";
}
};
version 2: 9ms 下面这种方法也是使用stringstream来做,但是我们使用了getline来做,第三个参数是设定分隔字符,我们用空格字符来分隔,这个跟上面的>>操作是有不同的,每次只能过一个空格字符,如果有多个空格字符连在一起,那么t会赋值为空字符串,所以我们在处理t的时候首先要判断其是否为空,是的话直接跳过,参见代码如下:
class Solution {
public:
void reverseWords(string &s) {
istringstream is(s);
s = "";
string tmp;
while (getline(is, tmp, ' ')) {
if (tmp.empty()) continue;
s = s.empty() ? tmp : (tmp + ' ' + s);
}
}
};