首页 > 代码库 > Reverse Words in a string
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.
Analyse: first reverse the entire string, then have wordBegin as the index for the starting position of the word, find the left and right index of a word, reverse from left to right, copy left to right to wordBegin, set ‘ ‘ to the next of that word, set correct index for wordBegin.
Be aware of the empty string, the length of word equals to 1.
Runtime: 9ms
1 class Solution { 2 public: 3 void reverseWords(string &s) { 4 if (s.empty()) return; 5 reverse(s.begin(), s.end()); 6 7 int left = 0, right = 0, wordBegin = 0; 8 int index = 0; 9 for (; index < s.size(); index++) {10 if (isspace(s[index])) continue;11 if (index == 0 || isspace(s[index - 1]))12 left = index;13 if (index == s.size() - 1 || isspace(s[index + 1])) right = index;14 else continue;15 16 reverse(s.begin() + left, s.begin() + right + 1);17 // leading 0s before the word18 if (wordBegin < left) {19 while (left <= right) {20 s[wordBegin++] = s[left++];21 }22 s[wordBegin] = ‘ ‘;23 wordBegin++;24 } else {25 wordBegin = right + 2;26 }27 }28 wordBegin = wordBegin ? wordBegin : 1;29 s.erase(s.begin() + wordBegin - 1, s.end());30 }31 };
Reverse Words in a string
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。