Generalized Abbreviation - Sinh tất cả viết tắt tổng quát của từ

Cho một từ, sinh tất cả các viết tắt tổng quát (thay thế các đoạn liên tiếp bằng độ dài đoạn). Không lặp lại.

Ví dụ: "word" → ["word","1ord","w1rd","wo1d","wor1","2rd","w2d","wo2","1o1d","1or1","w1r1","1o2","2r1","3d","w3","4"].

Giải thuật (Backtracking)

Duyệt từng vị trí, quyết định: giữ nguyên ký tự, hoặc bắt đầu/thêm vào một số (viết tắt). Dùng đệ quy, theo dõi chuỗi hiện tại và chỉ số. Tránh trùng lặp bằng cách chỉ tăng số khi ký tự trước là số.

Cài đặt C++

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

void print_vector(vector<string> v) {
    cout << "[";
    for (auto& s : v) cout << s << ", ";
    cout << "]" << endl;
}

class Solution {
public:
    vector<string> ret;

    void solve(string s, int idx) {
        if (idx >= s.size()) {
            ret.push_back(s);
            return;
        }
        string prefix = s.substr(0, idx);
        int i = prefix.size() - 1;
        string num = "";
        while (i >= 0 && isdigit(prefix[i])) {
            num = prefix[i] + num;
            i--;
        }
        if (i != (int)prefix.size() - 1) {
            // Ký tự trước là số, tăng số đó
            string newS = s.substr(0, idx - (prefix.size() - 1 - i)) + to_string(stoi(num) + 1) + s.substr(idx + 1);
            string s1 = to_string(stoi(num) + 1);
            string s2 = to_string(stoi(num));
            if (s1.size() == s2.size())
                solve(newS, idx);
            else
                solve(newS, idx + 1);
        } else {
            // Ký tự trước không phải số, bắt đầu số mới '1'
            char prev = s[idx];
            s[idx] = '1';
            solve(s, idx + 1);
            s[idx] = prev;
        }
        solve(s, idx + 1);
    }

    vector<string> generateAbbreviations(string word) {
        solve(word, 0);
        return ret;
    }
};

int main() {
    Solution ob;
    print_vector(ob.generateAbbreviations("hello"));
    return 0;
}

Đầu vào

hello

Đầu ra

[5, 4o, 3l1, 3lo, 2l2, 2l1o, 2ll1, 2llo, 1e3, 1e2o, 1e1l1, 1e1lo, 1el2, 1el1o, 1ell1, 1ello, h4, h3o, h2l1, h2lo, h1l2, h1l1o, h1ll1, h1llo, he3, he2o, he1l1, he1lo, hel2, hel1o, hell1, hello, ]