# [leetcode] Reverse Words in a String

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

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.

Force solution, o(n) time & space complexity. AC

```// I need a terminal to mark the end of the input string.
// return the original string if it contains only one word
// The string can not be longer than 2^32
// How about multiple spaces between words? Reduce them to a single space
// Could the input string contains leading or trailing spaces? Yes

//o(n) solution, force solution.
class Solution {
public:
void reverseWords(string &s) {
//extreme case
int length = s.size();
if(length == 0) return ;
string outputStr;
bool isInWord = false;
int start, end;
for(int i = s.size() - 1; i >= 0; i--){
char c = s[i];
if(c == ' '){
if(isInWord == false){
continue;
}
//in word, find the start of word
else{
isInWord = false;
start = i + 1;
appendStr(outputStr, s, start, end);
}
}
else{
if(isInWord == false){
//find the end of word
isInWord = true;
end = i;
}
else{
//in the word
}
}
}
if(isInWord == true){
appendStr(outputStr, s, 0, end);
}
s = outputStr;
}
void appendStr(string& re, string s, int start, int end){
if(re.size() > 0) re.push_back(' ');
re.append(s.substr(start, end - start + 1));
}
};```

O(1) in space, O(n) in time solution

Reverse the word in space. Handle the “index” words carefully.

```// I need a terminal to mark the end of the input string.
// return the original string if it contains only one word
// The string can not be longer than 2^32
// How about multiple spaces between words? Reduce them to a single space
// Could the input string contains leading or trailing spaces? Yes

//o(1) solution.
class Solution {
public:
void reverseWords(string &s) {
int len = s.size();
int proceedLen = 0;
int insertIndex = s.size();
while(proceedLen < len){
//find a word
bool isInWord = false;
int startIndex = -1;
int index = 0;
while(proceedLen + index < len){
char c = s[index];
if(c == ' '){
if(isInWord == false){
index++;
}
else{
//find the end of a word
thisLength = index - startIndex;
break;
}
}
else{
if(isInWord == false){
//find the beginning of a word
isInWord = true;
startIndex = index;
index++;
}
else{
//still in the word
index++;
}
}
}
//trailing spaces
if(startIndex == -1){
s.erase(0, index);
break;
}

//insert the word at the insertIndex
s.insert(insertIndex, s.substr(startIndex, index - startIndex));

//insert a space to seperate words
s.insert(insertIndex, " ");

//erase the parsed word
s.erase(0, index);

//update relative indexs
proceedLen += index;
insertIndex -= index;
}
//deal with extra inserted space
while(s[0] == ' '){
s.erase(0, 1);
}

}
};
```

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