Đảo ngược từ trong chuỗi II (Reverse Words in a String II) trong C++

Cho một mảng ký tự đại diện cho một chuỗi (các từ cách nhau bởi dấu cách). Yêu cầu: đảo ngược thứ tự các từ trong chính mảng đó (in-place), không dùng bộ nhớ thêm.

Ví dụ

Đầu vào: ['t','h','e',' ','m','a','n',' ','i','s',' ','n','i','c','e']
Đầu ra: ['n','i','c','e',' ','i','s',' ','m','a','n',' ','t','h','e']

Thuật toán hai bước (Two-step Reversal)

1. Đảo ngược toàn bộ mảng: Các từ giờ ở thứ tự ngược nhưng mỗi từ cũng bị đảo ngược ký tự.
2. Đảo ngược từng từ riêng lẻ: Duyệt mảng, mỗi khi gặp dấu cách (hoặc hết mảng), đảo ngược đoạn từ start đến i-1.

Triển khai C++

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

class Solution {
public:
    void reverseWords(vector<char>& s) {
        reverse(s.begin(), s.end()); // Bước 1
        int start = 0;
        for (int i = 0; i <= s.size(); ++i) {
            if (i == s.size() || s[i] == ' ') { // Bước 2
                reverse(s.begin() + start, s.begin() + i);
                start = i + 1;
            }
        }
    }
};

Độ phức tạp

• Thời gian: O(N) - mỗi ký tự được xử lý hằng số lần.
• Không gian: O(1) - thao tác in-place.

Kết quả kiểm thử

Đầu vào: {'t','h','e',' ','m','a','n',' ','i','s',' ','n','i','c','e'}
Đầu ra: [n, i, c, e, , i, s, , m, a, n, , t, h, e]