Leetcode:151.翻转字符串里的单词
给定一个字符串,逐个翻转字符串中的每个单词。
示例:
输入: "the sky is blue
", 输出: "blue is sky the
".
说明:
- 无空格字符构成一个单词。
- 输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括。
- 如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个。
进阶: 请选用C语言的用户尝试使用 O(1) 空间复杂度的原地解法。
解题思路:
这题是典型的字符串处理。涉及到的常用操作包括:
1. 删除字符串开始的所有空格。
while (int(s.size()) > 0 && s[0] == ' ') s.erase(0,1);
2. 删除字符串末的所有空格。
while (int(s.size()) > 0 && s[int(s.size()) - 1] == ' ') s.erase(int(s.size()) - 1,1);
3. 两个单词之间不能有多个空格,也就意味着没有两个或两个以上的连续空格。
4. 翻转一个字符串[left,right)区间的字符,特殊地,当left=0,right=s.size()时,翻转整个字符串。
void reverse_sub(int first, int last, string &s) {
while (first < last-1) {
swap(s[first++], s[last-- - 1]);
}
}
有了以上基本操作,本题就so easy了。解决本题主要有以下步骤:
1. 清除首尾的空格。
2. 将整个字符串翻转。
3. 翻转每个单词。
本次刷Leetcode有一个重大发现,该系统与正常的vs2015不兼容。string 类中erase函数,erase(int pos),删除数组下标为pos的字符。Leetcode中没有erase(int pos)函数的重载。但是幸好有erase(int pos,int size)删除字符串pos位置起的size个字符。虽然erase(int pos)不能用,但是可以用erase(int pos, 1)代替。
class Solution { public: void reverseWords(string &s) { //除去多余的空格 //除去首尾两端的空格 while (int(s.size()) > 0 && s[0] == ' ') s.erase(0,1); while (int(s.size()) > 0 && s[int(s.size()) - 1] == ' ') s.erase(int(s.size()) - 1,1); int i; //去除中间多余的空格 for (i = 1; i <= int(s.size()); i++) { if ((i<int(s.size())) && s[i - 1] == ' '&&s[i] == ' ') { s.erase(i - 1,1); i--; } } int size = s.size(); if (size <= 1) return; //翻转整个字符串 reverse_sub(0, size, s); //翻转每个单词 int first = 0, last = 0; for (i = 1; i <= size; i++) { if (s[i - 1] == ' ') { last = i - 1; reverse_sub(first, last, s); first = last + 1; } if (i == size) { reverse_sub(first, size, s); } } } void reverse_sub(int first, int last, string &s) { while (first < last-1) { swap(s[first++], s[last-- - 1]); } } }; |