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.
分析
给定一个字符串,以单词为单位对该字符串进行翻转,要求空间复杂度为O(1);
额外要求:
- 单词之间最多只能有一个空格,多余空格要删除;
- 字符串首尾不能添加多余空格;
方法一:此题的一个简单的解法,就是,我们可以借助vector,把字符串的单词按序加入容器,然后直接反转容器,再更新元字符串即可,但是此方法不符合空间复杂度的要求。
方法二:经过两步解决,首先,反转整个字符串,然后从前向后遍历,每经过一个单词,反转该单词一次。
当然在过程中,必须合理的处理多余空格问题。详见代码!
AC代码
class Solution {
public:
void reverseWords(string &s) {
if (s.empty())
return;
//首先,反转整个字符串
reverse(s.begin(), s.end());
int n = s.size();
//再反转每个单词,同时删除多余的空格,最终的字符串头尾不能是空格,且单词之间不能有多余的空格(最多一个)
string tmp = s;
s.clear();
//标记第一个单词,方便处理单词间的空格
bool flag = true;
for (int i = 0; i < n;)
{
//找到第一个非空格
if (tmp[i] == ' ')
{
++i;
continue;
}//if
string::iterator beg = tmp.begin() + i, end = tmp.begin();
for (int j = i; j < n; ++j)
{
//到达一个单词间的空格或者到整个字符串的结束
if (tmp[j] == ' ')
{
end += j;
reverse(beg, end);
//链接反转后的第一个单词
if (flag)
{
s = s + tmp.substr(i, j - i);
flag = false;
}
else{
s = s + " " + tmp.substr(i, j - i);
}
i = j + 1;
break;
}//if
if (j == n - 1)
{
reverse(beg, tmp.end());
if (flag)
{
s = s + tmp.substr(i, j - i + 1);
}
else{
s = s + " " + tmp.substr(i, j - i + 1);
}
i = j + 1;
break;
}
}//for
}//for
}
};
最新文章
- Shell命令_Cron使用
- matlab和C/C++混合编程--调用opencv
- 如何创建一个客户端回调:js获得服务端的内容?
- 微信公众号-开发者-自定义菜单-CLICK事件处理
- MongoDB的timezone问题
- cygwin设置中文
- linux ERROR: ld.so: object '/lib/libcwait.so' from /etc/ld.so.preload cannot be preloaded: ignored.
- 20个很有用的CSS技巧
- Spring Boot 系列教程8-EasyUI-edatagrid扩展
- webservice部署到服务器报错
- Mac下Kali虚拟机与宿主机共享文件夹
- 团队开发---”我爱淘“校园二手书店 NABC分析
- Mixins 混入选项操作
- (一)PHP简介
- webpack4 自学笔记二(typescript的配置)
- Linux中tty、pty、pts的概念区别 转载
- servlet-servletContext网站计数器
- 【BZOJ 4229】 4229: 选择 (线段树+树链剖分)
- [转] LINUX 三种网络连接模式
- maven打包错误:No compiler is provided in this environment. Perhaps you are running on a JRE rather than a JDK?