Sắp xếp lại từ trong câu (Rearrange Words in a Sentence) trong C++

Cho câu text (chữ cái đầu viết hoa, các từ cách nhau một dấu cách). Sắp xếp các từ theo độ dài tăng dần, giữ thứ tự gốc nếu độ dài bằng nhau. Trả về câu mới với chữ cái đầu viết hoa.

Ví dụ

Đầu vào: "I love to code in cpp"
Đầu ra: "I to in cpp love code"

Thuật toán

1. Chuyển ký tự đầu thành chữ thường.
2. Tách câu thành vector từ (dùng istringstream).
3. Tạo vector pair {từ, chỉ_số_gốc}.
4. Sắp xếp theo: độ dài tăng, nếu bằng thì chỉ số gốc tăng.
5. Ghép lại thành chuỗi, cách nhau dấu cách.
6. Viết hoa ký tự đầu.

Triển khai C++

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

class Solution {
    vector<string> split(string& s, char delim) {
        vector<string> res; string t;
        istringstream iss(s);
        while (getline(iss, t, delim)) res.push_back(t);
        return res;
    }
    static bool cmp(const pair<string,int>& a, const pair<string,int>& b) {
        if (a.first.size() != b.first.size()) return a.first.size() < b.first.size();
        return a.second < b.second;
    }
public:
    string arrangeWords(string text) {
        text[0] = tolower(text[0]);
        vector<string> words = split(text, ' ');
        vector<pair<string,int>> arr;
        for (int i = 0; i < words.size(); ++i) arr.emplace_back(words[i], i);
        sort(arr.begin(), arr.end(), cmp);
        string res;
        for (int i = 0; i < arr.size(); ++i) {
            res += arr[i].first;
            if (i + 1 < arr.size()) res += ' ';
        }
        res[0] = toupper(res[0]);
        return res;
    }
};

Độ phức tạp

• Thời gian: O(N log N) do sắp xếp, N số từ.
• Không gian: O(N) lưu vector từ và pair.

Kết quả kiểm thử

Đầu vào: "I love to code in cpp"
Đầu ra: I to in cpp love code