algo-aha

生成单词缩写

• https://leetcode.com/problems/generalized-abbreviation/

Write a function to generate the generalized abbreviations of a word.

Example:

Given word = "word", return the following list (order does not matter):

["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]

方法一：回溯，排列的写法（考虑位置idx的各种可能）

vector<string> generateAbbreviations(string word) {
    vector<string> ans;
    dfs(word, 0, 0, "", ans);
    return ans;
}

// count表示在word[idx..]之前有几个被省略还未输出
void search(const string &word, int idx, int count, string abbr, vector<string> &ans) {
    if (idx == word.size()) {
        if (count > 0) abbr += to_string(count);
        ans.push_back(abbr);
        return;
    }
    // 对每个字母，或者：省略它、并增加计数
    search(word, idx + 1, count + 1, abbr, ans);
    // 或者：计数>0时输出计数、再输出字母
    abbr += (count > 0 ? to_string(count) : "") + word[idx];
    search(word, idx + 1, 0, abbr, ans);
}

方法二：根据二进制01来选不选相应字母

联想：最短唯一单词缩写