557. Reverse Words in a String III

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;
    }
};