Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.
Example 1:
Input: "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"
Note: In the string, each word is separated by single space and there will not be any extra space in the string.
思路:善用c++STL的reverse模板算法.
template<class BidirectionalIterator>
void reverse(
BidirectionalIterator _First,
BidirectionalIterator _Last
);
参数:
_First
指向第一个元素的位置的双向迭代器在元素交换的范围。
_Last
指向通过最终元素的位置的双向迭代器在元素交换的范围。
即:反转(first,last-1)区间内的元素顺序.
思路2:整个串s先反转一次,然后每个单词各自反转一次,类似于"矩阵转置等价于分块子矩阵转置加子矩阵间(位置)转置"的原理.但实现起来不简单.
class Solution { //思路1
public:
string reverseWords(string s) {
for (int i = 0; i < s.length(); i++) {
if (s[i] != ' ') { //i指向第一个非空格
int j = i;
for (; j < s.length() && s[j] != ' '; j++) {} //j指向下一个空格
reverse(s.begin()+i, s.begin()+j);//反转(i,j-1)之间的元素
i = j; // 更新i
}
}
return s;
}
};
