[LeetCode]151.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.

思路

两次反转法。这里注意单词之间的多个空格只留一个空格以及去掉前导0和后导0。

代码

/*—————————————* 日期：2015-05-05* 作者：SJF0115* 题目: 151.Reverse Words in a String* 网址：https://leetcode.com/problems/reverse-words-in-a-string/* 结果：AC* 来源：LeetCode* 博客：—————————————–*/#include <iostream>#include <vector>using namespace std;:void reverseWords(string &s) {int size = s.size();if(size <= 0){return;}= 0;while(s[index] == ‘ ‘){++index;}//whileint left = index;// 后导0index = size – 1;while(s[index] == ‘ ‘){–index;}//whileint right = index;// 连续空格只保留一个for(int i = left;i <= right;){if(i > left && s[i-1] == ‘ ‘ && s[i] == ‘ ‘){s.erase(i-1,1);–right;}//ifelse{++i;}}start = left,end = left;for(int i = left;i <= right+1;++i){if(i == right+1 || s[i] == ‘ ‘){Reverse(s,start,end-1);++end;start = end;}//ifelse{++end;}//else}//for// 整体翻转Reverse(s,left,right);s = s.substr(left,right – left + 1);}private:void Reverse(string &str,int start,int end){for(int i = start,j = end;i < j;++i,–j){swap(str[i],str[j]);}//for}};int main() {Solution solution;//string str(” abc cdef “);string str(” a vvv “);solution.reverseWords(str);cout<<str<<endl;}

运行时间

代码二

/*—————————————* 日期：2015-05-05* 作者：SJF0115* 题目: 151.Reverse Words in a String* 网址：https://leetcode.com/problems/reverse-words-in-a-string/* 结果：AC* 来源：LeetCode* 博客：—————————————–*/#include <iostream>#include <algorithm>using namespace std;:void reverseWords(string &s) {int size = s.size();if(size <= 0){return;}= size – 1;string str;while(index >= 0){// 空格while(index >= 0 && s[index] == ‘ ‘){–index;}//whileif(index < 0){break;}//ifif(str.size() != 0){str.push_back(‘ ‘);}//ifstring tmp;while(index >= 0 && s[index] != ‘ ‘){tmp.push_back(s[index]);–index;}(tmp.begin(),tmp.end());str.append(tmp);}//whiles = str;}};int main() {Solution solution;string str(” abc cdef “);//string str(” a “);solution.reverseWords(str);cout<<str<<endl;}

运行时间

，你被雨淋湿的心，是否依旧。