leetcode:557 反转字符串的单词
题目来源:leetcode
题目描述:给定一个字符串,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。
例如:
输入: “Let’s take LeetCode contest” |
---|
输出: “s’teL ekat edoCteeL tsetnoc” |
这道题的测试用例很长,一般的两个循环式跑不过的,以下是其中一部分测试用例,后面还有很长
常规的两个循环,测试用例是跑不过的例如下面:
class Solution {
public:
string reverseWords(string s) {
int begin=0;
int end=0;
while(s[begin]!='\0')
{
int tmp=end;
if(s[end]==' '||s[end]=='\0')
{ end--;
while(begin<end)
{
char t=' ';
t=s[begin];
s[begin]=s[end];
s[end]=t;
begin++;
end--;
}
end=tmp;
end++;
begin=end;
}
end++;
}
return s;
}
};
所以我们需要采用另一种方法,用空间换时间,新开一个str,把反转的单词放到str中,代码如下:
class Solutin{
public:
string reverseWords(string s) {
if(s.size()<=1)
return s;
int begin=0;
int end=0;
int i;
string str;//开一个新的str
while(1)
{
while(end<s.size()&&s[end]!=' ')
end++;//找到空格就停下
for(i=end-1;i>=begin;i--)
{
str+=s[i];//把该单词的从尾到头赋值给str
}
if(end!=s.size())
{
str+=' ';//把空格赋值给str
}
else
break;//当end走到s的尾时跳出
begin=end+1;//把begin指向下一个单词的第一个位置
end++;
}
return str;//返回str
}
};
这样这个最长的测试用例也就可以跑的过了。