首页 > 代码库 > [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
".
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.
原题地址
二、解题思想
翻转字符串中的单词顺序,这是个老题目了,但是leetcode上面的要求更为严格,如:
要求把开头和结尾的空格删除掉;
缩减单词间的空格数为1(如果有多个空格);
单词若全是空格,则返回一个空字符串("").
此题思想不难,主要是注意上面三个要求和一些细节就可以AC。
大致分为两步:一个是常规的翻转字符串中的单词;另一个就是想方法去掉串中的多余的单词;这两步骤的顺序可以颠倒。
下面给出两份代码,第一个代码是先去掉多余的空格,然后在翻转;第二个代码先翻转,在去掉多余的空格。就效率上来说应该是第一个代码的效率更高。
三、代码实现
代码一:
class Solution { public: void reverseWords(string &s) { if(s.size()<=0) return ; char *work = new char[s.size()+1]; //reduce blank int j=0; for(int i=0; s[i]!='\0'; ++i){ if(i>0 && s[i] == ' ' && s[i-1]!= ' ') work[j++] = s[i]; else if(s[i] != ' ') work[j++] = s[i]; } if(j>0 && work[j-1]==' ') work[--j] = '\0'; else work[j] = '\0'; //reverse all string reverse(work, 0, j-1); int p= 0, i=0; //reverse each word while(i<j){ while(p<j && work[p]!=' ') p++; reverse(work, i, p-1); i = p+1; p = i; } string temp(work); s = temp; } void reverse(char *s, int beg, int end){ while(beg < end){ char temp = s[beg]; s[beg++] = s[end]; s[end--] = temp; } } };
代码二:
class Solution { public: void reverseWords(string &s) { int n = s.size(); if(n<=0) return; //if(n==1) //reverse the whole string reverse(s, 0, n-1); //reverse each word int begin=0, end = 0; while(begin<n){ while( begin< n && s[begin] == ' ') ++begin; end = begin; while( end<n && s[end] != ' ') ++end; reverse(s, begin, end-1); begin = end; } //reduce blank begin = 0; while(begin<n && s[begin] ==' ') ++begin; if(begin == n) {s = s.substr(0,0);return;} end = n-1; while(end>=0 && s[end] == ' ') --end; int start = 0; char pre; for(; begin<=end; ++begin){ if(s[begin] != ' '){ s[start++] = s[begin]; pre = s[begin]; }else{ if(pre != ' '){ s[start++] = ' '; pre = ' '; } } } if(start != n) s = s.substr(0, start); } void reverse(string &s, int begin, int end){ char temp; while(begin<end){ temp = s[begin]; s[begin++] = s[end]; s[end--] = temp; } } };
如果你觉得本篇对你有收获,请帮顶。
另外,我开通了微信公众号--分享技术之美,我会不定期的分享一些我学习的东西.
另外,我开通了微信公众号--分享技术之美,我会不定期的分享一些我学习的东西.
你可以搜索公众号:swalge 或者扫描下方二维码关注我
(转载文章请注明出处: http://blog.csdn.net/swagle/article/details/28236933 )
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。