LeetCode|Reverse Words in a String

2016-12-02 12:52:38来源:网络收集作者:小城故事人点击

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 trailingspaces.
- How about multiple spaces between two words? Reduce them to a single space in the reversed string.

思路:
双指针,p2遍历到合法内容后p1写入。找到每个单词单独反转单词,最后再把整个句子反转就是答案。
需要FSM的思想,找到几种状态:


'/0'
空格+'/0'
空格+单词+'/0'
单词+'/0'
单词+空格+'/0'
空格+单词+空格'/0'void reverseWord(char *s, char *e){
while(s < e){
char tmp = *s;
*s++ = *e;
*e-- = tmp;
}
}
void reverseWords(char *str) {
if(str == NULL || *str == '/0') return;
char *p1 = str, *s = p1, *e, *p2 = str;
while(*p2 == ' ') p2++; // w***
if(*p2 == '/0') {
*str = '/0'; // 日了狗了:[ ]
return;
}
while(*p2 != '/0'){// case1: c'/0'
if(*p2 != ' '){// case2: cw'/0' // cout << "字母 " << *p1 << endl;
*p1++ = *p2++;
if(*p2 == '/0') reverseWord(s, p1-1);
} else {// cout << "遇到空格 : ";
e = p1-1;
reverseWord(s, e);
while(*p2 == ' ') p2++;
if(*p2 != '/0'){ // character
*p1++ = ' ';
s = p1;
} //else{}// '/0'
}
} *p1 = '/0';
reverseWord(str, p1-1);//if(*str == '/0') return;
}

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台