# LeetCode Reverse Words in a String

LeetCode 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.

class Solution {
public:
void reverseWords(string &s) {
string ans = "";
int start = 0, end = 0, n = s.size();
while (true) {
while (start < n&&s[start] == ' ')++start;
if (start >= n)break;
end = start + 1;
while (end < n&&s[end] != ' ')++end;
if (end >= n)break;
ans = s.substr(start, end - start) + " " + ans;
start = end + 1;
}
if (end > start)ans = s.substr(start, end - start) + " " + ans;
s = ans.substr(0, ans.size() - 1);
}
};

class Solution {
public:
void reverseWords(string &s) {
reverse(s.begin(), s.end());
//i,j为新字符串每个单词的首尾位置，u,v为旧字符串每个单词的首尾位置
int i = 0, j = 0, u = 0, v = 0, n = s.size();
while (true) {
while (u < n&&s[u] == ' ')++u;
if (u >= n)break;
v = u;
while (v < n&&s[v] != ' ')s[j++] = s[v++];
reverse(s.begin() + i, s.begin() + j);
if (v >= n)break;
s[j++] = ' ';
i = j;
u = v;
}
if (j == 0)s = "";
else if (s[j - 1] == ' ')s.resize(j - 1);
else s.resize(j);
}
};

This site uses Akismet to reduce spam. Learn how your comment data is processed.