โปรแกรมกลับลำดับคำในประโยคที่เก็บเป็น character array ใน C++

ภาพรวมปัญหา

ให้ประโยคเก็บเป็น vector<char> (แต่ละตัวอักษรและ space แยกกัน) ต้องการกลับลำดับคำในประโยค

ตัวอย่าง

Input: {'t','h','e',' ','m','a','n',' ','i','s',' ','n','i','c','e'}

Output: {'n','i','c','e',' ','i','s',' ','m','a','n',' ','t','h','e'}

คำแปล: "the man is nice" → "nice is man the"

แนวทางแก้ปัญหา (Two-Pass Reverse)

1. Reverse ทั้ง array → "ecin si nam eht"
2. Reverse แต่ละคำแยกกัน → "nice is man the"

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

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

void print_vector(vector<char> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << ", ";
    }
    cout << "]" << endl;
}

class Solution {
public:
    void reverseWords(vector<char>& s) {
        reverse(s.begin(), s.end()); // ขั้นตอนที่ 1: กลับทั้งหมด
        
        int j = 0; // เริ่มต้นของคำปัจจุบัน
        int n = s.size();
        
        for (int i = 0; i < n; i++) {
            if (s[i] == ' ') { // เจอ space = จบคำ
                reverse(s.begin() + j, s.begin() + i); // กลับคำนี้
                j = i + 1; // เริ่มคำถัดไป
            }
        }
        reverse(s.begin() + j, s.begin() + n); // กลับคำสุดท้าย
    }
};

int main() {
    Solution ob;
    vector<char> v = {'t','h','e',' ','m','a','n',' ','i','s',' ','n','i','c','e'};
    ob.reverseWords(v);
    print_vector(v);
    return 0;
}

ผลลัพธ์

[n, i, c, e, , i, s, , m, a, n, , t, h, e, ]

การทำงานทีละขั้น

1. Original: [t,h,e, ,m,a,n, ,i,s, ,n,i,c,e]
2. After full reverse: [e,c,i,n, ,s,i, ,n,a,m, ,e,h,t]
3. Reverse word 1 (0-3): [n,i,c,e, ,s,i, ,n,a,m, ,e,h,t]
4. Reverse word 2 (5-6): [n,i,c,e, ,i,s, ,n,a,m, ,e,h,t]
5. Reverse word 3 (8-10): [n,i,c,e, ,i,s, ,m,a,n, ,e,h,t]
6. Reverse word 4 (12-14): [n,i,c,e, ,i,s, ,m,a,n, ,t,h,e]

ความซับซ้อน

• เวลา: O(N) — reverse ทั้ง array 1 ครั้ง + reverse แต่ละคำ 1 ครั้ง
• พื้นที่: O(1) — in-place

ข้อดีของวิธีนี้

• In-place ไม่ต้อง allocate memory เพิ่ม
• ใช้ STL algorithm `reverse` เข้าใจง่ายและมีประสิทธิภาพ
• เป็น classic interview question (Reverse Words in a String)