首页 > 代码库 > Reverse Words in a String （4）
Reverse Words in a String （4）
Given an input string, reverse the string word by word.
For example,
Given s = "the sky is blue",
return "blue is sky the".
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 sp
ace in the reversed string.//要将单词之间的空格减少为1个
首先是最朴素的解法，利用堆栈，将所有的单词压入一个堆栈，最后再逐个pop出来，这样就能够得到反序单词的句子。单词压入堆栈的过程中，利用了单词中间没有空格的性质。思想很简单，但是在事实过程中还是出现了一点小曲折，弄了2,3次才最终accepted。
上代码：
1 class Solution{ 2 public: 3 void reverseWords(string &s){ 4 int len=s.length(); 5 int i; 6 stack <string> end; 7 i=-1; 8 string ss=""; 9 int sum=0;10 while(1){11 i++;12 if(i>(len-1))13 break;14 if(s[i]==‘ ‘){//15 if(ss.length()){//说明ss中储存的单词还没有压入堆栈，将其压入堆栈16 sum++;//sum用于记录string中总共有多少个单词17 end.push(ss);18 ss="";19 }20 continue;21 }22 else if(s[i]!=‘ ‘){23 ss.push_back(s[i]);//将单词中的字母放入存放单词的string中24 }25 }26 if(ss.length()){//说明最后最后遗留了一个单词还没有压入堆栈，将其压入堆栈27 end.push(ss);28 sum++;29 }30 if(!sum){//如果单词数量为0，说明原来输入的string中字符全为空格，或者为空。返回空值31 s="";32 return;33 }34 s="";35 for(i=0;i<sum;i++){36 s+=end.top();37 s+=" ";38 end.pop();39 }40 s.pop_back();//因为单词末尾不能有空格，将最后的空格弹出41 42 }43 44 };
但是上述方法过程感觉稍微有点繁杂，有必要采取另外一种思路。
首先上代码：
1 class Solution { 2 public: 3 void reverseWords(string &s) { 4 int i=s.length(); 5 i--; 6 string ss; 7 while(i>=0){ 8 while(i>=0&&s[i]==‘ ‘) 9 i--;//消除多余的空格10 if(i<0)11 break;12 if(ss.length()!=0)//如果记录返回值的ss长度不为013 ss.push_back(‘ ‘);//将‘ ‘压入其中14 string temp;15 for(i;i>=0&&s[i]!=‘ ‘;i--)16 temp.push_back(s[i]);//反序压入单词所有字母17 reverse(temp.begin(),temp.end());//回复单词字母的顺序18 ss.append(temp);//将单词加入ss19 }20 s=ss;//返回值为ss21 22 23 24 }//返回值直接储存在s中了25 };
上述代码感觉思路非常好，其精妙之处在与采取反序来处理字符串。再加上充分利用reverse，append等库函数，使得代码清晰易懂。
Reverse Words in a String （4）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。