解法1: 栈

class Solution {
  public:
    string ReverseSentence(string str) {
        int len = str.length();
        if (len == 0) return "";
        stack<string> s; // 注意压栈的是单词

        for (int i = 0; i < len; ++i) {
            int j = i;
            while (j < len && str[j] != ' ') j++; // 跳过空格
            // cout << "i == " << i << ", j == " << j << endl;
            s.push(str.substr(i, j - i));
            i = j;  // 跳过空格
        }
       
        string result = "";
        while (!s.empty()) {
            result += s.top();
            s.pop();
            if (!s.empty()) {
                result += " ";
            }
        }
        return result;
    }
};
// 0123456789
// nowcoder. a am I

解法2: 双指针

// 0123456789abcdef
// nowcoder. a am I
//
class Solution {
  public:
    string ReverseSentence(string str) {
        int len = str.length();
        if (len == 0) return "";
        int i = len - 1;
        int j = i;
        string result = "";
        while (i >= 0) {
            if (i != len - 1) {  // 处理空格
                result += " ";
            }
            while (i >= 0 && str[i] != ' ') i--;
            cout << "i == " << i << ", j == " << j << endl;
            result += str.substr(i+1, j - i);
            while (i >= 0 && str[i] == ' ') i--;
            j = i;
        }
        return result;
    }
};