Reverse Words in a String ใน C++ : กลับลำดับคำในประโยค

ให้ String s มีหลายคำ (คั่นด้วย Space) กลับ **ลำดับคำ** (ไม่ใช่กลับตัวอักษรในคำ) และจัดการ Space ให้ถูกต้อง (ไม่มี Leading/Trailing/Multiple Spaces)

ตัวอย่าง

Input: "The quick brown fox jumps over a lazy dog"

Output: "dog lazy a over jumps fox brown quick The"

แนวทาง: Two-Pass Reverse (In-Place Style)

1. Trim & Normalize: ลบ Leading/Trailing Spaces, รวม Multiple Spaces -> Single Space (Helper getString)
2. Reverse Entire String: reverse(s.begin(), s.end()) -> คำและตัวอักษรในคำกลับหมด
3. Reverse Each Word: Scan หา Word Boundaries (Space-delimited) -> Reverse ตัวอักษรในแต่ละคำคืนมา (reverseWordss)

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    string reverseWords(string s) {
        reverse(s.begin(), s.end());     // 1. Reverse all
        reverseWordss(s);                // 2. Reverse each word
        return getString(s);             // 3. Clean up spaces
    }

    // Helper: Trim & Normalize spaces
    string getString(string s) {
        int i = 0, j = s.size() - 1;
        while (i < s.size() && s[i] == ' ') i++;
        while (j >= 0 && s[j] == ' ') j--;
        string ret = "";
        for (; i <= j; i++) {
            if (!ret.empty() && ret.back() == ' ' && s[i] == ' ') continue; // Skip multi-space
            ret += s[i];
        }
        return ret;
    }

    // Helper: Reverse each word in-place
    void reverseWordss(string& s) {
        int j = 0;
        for (int i = 0; i < s.size(); i = j) {
            if (s[i] == ' ') { j = i + 1; continue; }
            while (j + 1 < s.size() && s[j + 1] != ' ') j++;
            // Reverse s[i..j]
            int x = i, y = j;
            while (x < y) swap(s[x++], s[y--]);
            j++;
        }
    }
};

Input / Output

Input:  "The quick brown fox jumps over a lazy dog"
Output: "dog lazy a over jumps fox brown quick The"

ความซับซ้อน (Complexity)

• Time: O(N) — ผ่าน String จำนวนคงที่รอบ
• Space: O(N) — สำหรับ Result String (In-place ใน Array จริงได้ O(1))

วิธีอื่น (Simpler)

Split by Space -> Vector -> Reverse Vector -> Join with Space (C++ ต้องทำเองหรือ用 stringstream) วิธี Two-Pass Reverse นี้เป็น Classic In-Place Algorithm ครับ