320. Generalized Abbreviation

題目網址：https://leetcode.cn/problems/generalized-abbreviation/

題意：寫一函式來生成一個單字的通用縮寫, 以任意順序返回。

Solution 1：

想法：每個 char 都有「取縮寫 or 不取縮寫」兩種選擇, 其中用 num 代表在 word[i] 前面取縮寫的連續 char 數

• 取縮寫：i + 1, 且 num + 1, 並進入下一輪遞迴
• 不取縮寫：
  • 若 num != 0：
    • 將 num 加入到 cur 中, 並將 num 歸零
    • 將 word[i] 加入到 cur 中, 並進入下一輪遞迴
  • 若 num == 0：
    • 將 num 歸零
    • 將 word[i] 加入到 cur 中, 並進入下一輪遞迴

class Solution {
public:
    vector<string> generateAbbreviations(string word) {
        string cur;
        dfs(word, 0, word.size(), cur, 0);
        return res;
    }

private:
    vector<string> res;

    void dfs(const string& word, const int i, const int n, string cur, const int num){
        if (i == n) {
            if (num != 0) {
                cur += to_string(num);
            }
            res.emplace_back(cur);
            return;
        }

        // word[i] 取縮寫
        dfs(word, i + 1, n, cur, num + 1);

        // word[i] 不取縮寫（共通點：word[i] 加入到 cur 中, 故將 word[i] 提出）
        cur += (num == 0 ? "" : to_string(num)) + word[i];
        dfs(word, i + 1, n, cur, 0);
    }
};

• time：$O(n\cdot 2^n)$
  • 每個 char 都有兩種選擇 ➔ 總共 $2^n$ 種
  • 建構每一種需 $O(n)$
• space：$O(n)$ ➔ 若不考慮要返回的 array res, 則取決於遞迴深度, 最大遞迴深度為 n

Solution 2：

想法：同 Solution 1, 由於本題不需剪枝, 且每個 char 都有「取縮寫 or 不取縮寫」兩種選擇, 故用 Bit Manipulation 比較方便（狀態壓縮）。

• 首先, 遍歷 00...0 到 11...1 所有 n 位的二進位狀態（所有 char 的選擇總共有 $2^n$ 種）, 並定義：
  • 若某 bit 為 0, 就代表對應位置的 char 不取縮寫
  • 若某 bit 為 1, 就代表對應位置的 char 取縮寫
• 若第 i 個 bit 要取縮寫：
  • 往後遍歷也要縮寫的連續 char, 直到遇到不縮寫的 char（假設其 index = j）
  • 將縮寫的長度加入到 cur 中
  • 將 i 設為 j - 1 ➔ 下一輪循環, i 將從 j 開始往後遍歷
• 若第 i 個 bit 不取縮寫：
  • 將 word[i] 加入到 cur 中, 並進入下一輪遞迴

class Solution {
public:
    vector<string> generateAbbreviations(string word) {
        const int n = word.size();
        vector<string> res;

        for (int state = 0; state < (1 << n); ++state) { // 遍歷所有二進位狀態
            string cur;

            for (int i = 0; i < n; ++i) { // 遍歷該狀態所有 char 是否要縮寫
                i f((state >> i) & 1) { // 若第 i 個 char 要縮寫
                    // 往後遍歷也要縮寫的連續 char, 直到遇到不縮寫的 char
                    int j = i;
                    while (j < n && (state >> j) & 1) {
                        ++j;
                    }

                    const int len = j - i; // 縮寫的長度
                    cur += to_string(len);
                    i = j - 1; // 下一輪 i 從 j 開始繼續往後遍歷 char
                } else {
                    cur += word[i];
                }
            }

            res.emplace_back(cur);
        }

        return res;
    }
};

• time：$O(n\cdot 2^n)$
  • 每個 char 都有兩種選擇 ➔ 總共 $2^n$ 種
  • 建構每一種需 $O(n)$
• space：$O(n)$ ➔ 若不考慮要返回的 array res, 則取決於 cur 的長度（cur 長度不超過 n）