// 演算法：用 stringstream 以空白為分隔讀出每個單字到 vector，
// 然後從後往前接起來，中間補一個空白。O(n) 時間，O(n) 額外空間。
// Algorithm: use a stringstream to tokenize on whitespace into a vector,
// then concatenate from back to front with single-space separators.
// O(n) time, O(n) extra space.

#include <string>     // std::string
#include <sstream>    // std::istringstream — 讓我們像讀 cin 一樣從字串讀出 token
#include <vector>     // std::vector — 動態陣列 / dynamic array

class Solution {
public:
    std::string reverseWords(std::string s) {
        std::istringstream iss(s);         // 把 s 包成「字串流」/ wrap s as an input stream
        std::vector<std::string> words;    // 存放每個單字 / will hold each parsed word
        std::string word;                  // 暫存當前讀到的單字 / buffer for the current token

        // operator>> 會自動跳過任何空白並讀出下一個非空白 token，
        // 所以多重空白、前導/尾隨空白都會被自動忽略。
        // operator>> automatically skips any whitespace and extracts the next
        // non-space token — extra/leading/trailing spaces are handled for free.
        while (iss >> word) {              // 持續讀直到沒有 token / loop until no token left
            words.push_back(word);         // 把這個單字放進 vector 尾端 / append to vector
        }

        std::string result;                // 最終答案字串 / output string
        result.reserve(s.size());          // 預先配置空間，避免多次重新配置 / reserve to avoid reallocs

        // 從最後一個單字往前走 / iterate from the last word back to the first.
        // (int) 轉型是為了讓 i 可以變成 -1 而不會繞回去（size_t 是無號的）。
        // The (int) cast lets i go to -1 safely; size_t is unsigned and would wrap.
        for (int i = (int)words.size() - 1; i >= 0; --i) {
            result += words[i];            // 接上這個單字 / append the word
            if (i > 0) {                   // 若不是最後一次（即還有後續單字要接）/ if more words follow
                result += ' ';             // 補一個分隔空白 / add a single-space separator
            }
        }

        return result;                     // 回傳組合好的結果 / return the assembled string
    }
};