320. 列举单词的全部缩写 🔒

题目描述

单词的 广义缩写词 可以通过下述步骤构造：先取任意数量的 不重叠、不相邻 的子字符串，再用它们各自的长度进行替换。

• 例如，"abcde" 可以缩写为：
  • "a3e"（"bcd" 变为 "3" ）
  • "1bcd1"（"a" 和 "e" 都变为 "1"）
  • "5" ("abcde" 变为 "5")
  • "abcde" (没有子字符串被代替)
• 然而，这些缩写是 无效的 ：
  • "23"（"ab" 变为 "2" ，"cde" 变为 "3" ）是无效的，因为被选择的字符串是相邻的
  • "22de" ("ab" 变为 "2" ， "bc" 变为 "2")  是无效的，因为被选择的字符串是重叠的

给你一个字符串 word ，返回 一个由 word 的所有可能 广义缩写词 组成的列表 。按 任意顺序 返回答案。

 

示例 1：

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

示例 2：

输入：word = "a"
输出：["1","a"]

 

提示：

• 1 <= word.length <= 15
• word 仅由小写英文字母组成

解法

方法一：DFS

我们设计一个函数 \(dfs(i)\)，表示对于字符串 \(word[i:]\)，返回其所有可能的缩写。

函数 \(dfs(i)\) 的执行逻辑如下：

如果 \(i \geq n\)，说明已经处理完了字符串 \(word\)，直接返回一个空字符串组成的列表。

否则，我们可以选择保留 \(word[i]\)，然后对 \(dfs(i + 1)\) 返回的列表中的每个字符串前面添加 \(word[i]\)，将得到的结果添加到答案中。

我们也可以选择删除 \(word[i]\) 及其后面的若干个字符，假设我们删除了 \(word[i..j)\)，那么第 \(j\) 个字符不删除，然后对 \(dfs(j + 1)\) 返回的列表中的每个字符串前面添加 \(j - i\)，将得到的结果添加到答案中。

最后，我们在主函数中调用 \(dfs(0)\) 即可。

时间复杂度 \(O(n \times 2^n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 是字符串 \(word\) 的长度。

Python3JavaC++GoTypeScript

class Solution:
    def generateAbbreviations(self, word: str) -> List[str]:
        def dfs(i: int) -> List[str]:
            if i >= n:
                return [""]
            ans = [word[i] + s for s in dfs(i + 1)]
            for j in range(i + 1, n + 1):
                for s in dfs(j + 1):
                    ans.append(str(j - i) + (word[j] if j < n else "") + s)
            return ans

        n = len(word)
        return dfs(0)

class Solution {
    private String word;
    private int n;

    public List<String> generateAbbreviations(String word) {
        this.word = word;
        n = word.length();
        return dfs(0);
    }

    private List<String> dfs(int i) {
        if (i >= n) {
            return List.of("");
        }
        List<String> ans = new ArrayList<>();
        for (String s : dfs(i + 1)) {
            ans.add(String.valueOf(word.charAt(i)) + s);
        }
        for (int j = i + 1; j <= n; ++j) {
            for (String s : dfs(j + 1)) {
                ans.add((j - i) + "" + (j < n ? String.valueOf(word.charAt(j)) : "") + s);
            }
        }
        return ans;
    }
}

class Solution {
public:
    vector<string> generateAbbreviations(string word) {
        int n = word.size();
        function<vector<string>(int)> dfs = [&](int i) -> vector<string> {
            if (i >= n) {
                return {""};
            }
            vector<string> ans;
            for (auto& s : dfs(i + 1)) {
                string p(1, word[i]);
                ans.emplace_back(p + s);
            }
            for (int j = i + 1; j <= n; ++j) {
                for (auto& s : dfs(j + 1)) {
                    string p = j < n ? string(1, word[j]) : "";
                    ans.emplace_back(to_string(j - i) + p + s);
                }
            }
            return ans;
        };
        return dfs(0);
    }
};

func generateAbbreviations(word string) []string {
    n := len(word)
    var dfs func(int) []string
    dfs = func(i int) []string {
        if i >= n {
            return []string{""}
        }
        ans := []string{}
        for _, s := range dfs(i + 1) {
            ans = append(ans, word[i:i+1]+s)
        }
        for j := i + 1; j <= n; j++ {
            for _, s := range dfs(j + 1) {
                p := ""
                if j < n {
                    p = word[j : j+1]
                }
                ans = append(ans, strconv.Itoa(j-i)+p+s)
            }
        }
        return ans
    }
    return dfs(0)
}

function generateAbbreviations(word: string): string[] {
    const n = word.length;
    const dfs = (i: number): string[] => {
        if (i >= n) {
            return [''];
        }
        const ans: string[] = [];
        for (const s of dfs(i + 1)) {
            ans.push(word[i] + s);
        }
        for (let j = i + 1; j <= n; ++j) {
            for (const s of dfs(j + 1)) {
                ans.push((j - i).toString() + (j < n ? word[j] : '') + s);
            }
        }
        return ans;
    };
    return dfs(0);
}

方法二：二进制枚举

由于字符串 \(word\) 的长度不超过 \(15\)，因此我们可以使用二进制枚举的方法枚举所有的缩写。我们用一个长度为 \(n\) 的二进制数 \(i\) 表示一种缩写方式，其中 \(0\) 表示保留对应的字符，而 \(1\) 表示删除对应的字符。我们在 \([0, 2^n)\) 的范围内枚举所有 \(i\)，并将其转换成对应的缩写，添加到答案列表中即可。

时间复杂度 \(O(n \times 2^n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 是字符串 \(word\) 的长度。

Python3JavaC++Go

class Solution:
    def generateAbbreviations(self, word: str) -> List[str]:
        n = len(word)
        ans = []
        for i in range(1 << n):
            cnt = 0
            s = []
            for j in range(n):
                if i >> j & 1:
                    cnt += 1
                else:
                    if cnt:
                        s.append(str(cnt))
                        cnt = 0
                    s.append(word[j])
            if cnt:
                s.append(str(cnt))
            ans.append("".join(s))
        return ans

class Solution {
    public List<String> generateAbbreviations(String word) {
        int n = word.length();
        List<String> ans = new ArrayList<>();
        for (int i = 0; i < 1 << n; ++i) {
            StringBuilder s = new StringBuilder();
            int cnt = 0;
            for (int j = 0; j < n; ++j) {
                if ((i >> j & 1) == 1) {
                    ++cnt;
                } else {
                    if (cnt > 0) {
                        s.append(cnt);
                        cnt = 0;
                    }
                    s.append(word.charAt(j));
                }
            }
            if (cnt > 0) {
                s.append(cnt);
            }
            ans.add(s.toString());
        }
        return ans;
    }
}

class Solution {
public:
    vector<string> generateAbbreviations(string word) {
        int n = word.size();
        vector<string> ans;
        for (int i = 0; i < 1 << n; ++i) {
            string s;
            int cnt = 0;
            for (int j = 0; j < n; ++j) {
                if (i >> j & 1) {
                    ++cnt;
                } else {
                    if (cnt) {
                        s += to_string(cnt);
                        cnt = 0;
                    }
                    s.push_back(word[j]);
                }
            }
            if (cnt) {
                s += to_string(cnt);
            }
            ans.push_back(s);
        }
        return ans;
    }
};

func generateAbbreviations(word string) (ans []string) {
    n := len(word)
    for i := 0; i < 1<<n; i++ {
        s := &strings.Builder{}
        cnt := 0
        for j := 0; j < n; j++ {
            if i>>j&1 == 1 {
                cnt++
            } else {
                if cnt > 0 {
                    s.WriteString(strconv.Itoa(cnt))
                    cnt = 0
                }
                s.WriteByte(word[j])
            }
        }
        if cnt > 0 {
            s.WriteString(strconv.Itoa(cnt))
        }
        ans = append(ans, s.String())
    }
    return
}

评论