0320. 列举单词的全部缩写

ITCharge大约 3 分钟

---

0320. 列举单词的全部缩写

标签：位运算、字符串、回溯
难度：中等

题目链接

0320. 列举单词的全部缩写 - 力扣

题目大意

描述：

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

例如，"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 \le word.length \le 15$ 。
$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：回溯算法

这道题的核心思想是：使用回溯算法枚举每个字符位置的选择，要么保留原字符，要么作为数字的一部分。

解题步骤：

定义状态：设当前处理到位置 $i$ ，当前缩写字符串为 $current$ ，上一个位置是否为数字为 $is\_prev\_digit$ 。
递归决策：对于位置 $i$ $i$ 的字符，有两种选择：
- 保留字符：将字符直接添加到当前缩写中。
- 作为数字：如果上一个位置不是数字，则开始一个新的数字计数；如果上一个位置是数字，则继续当前数字计数。
回溯处理：每次选择后递归处理下一个位置，递归返回后撤销选择。
终止条件：当处理完所有字符时，将当前缩写加入结果列表。

关键点：

数字不能相邻，即不能出现 "22de" 这样的情况。
数字不能重叠，即不能出现 "23" 这样的情况。
需要跟踪上一个位置是否为数字，以决定是否可以开始新的数字计数。

算法正确性：

设字符串长度为 $n$ ，每个位置有 2 种选择（保留字符或作为数字），总共有 $2^n$ 种可能的组合。回溯算法会枚举所有有效的组合，确保不遗漏任何可能的缩写。

思路 1：代码

from typing import List

class Solution:
    def generateAbbreviations(self, word: str) -> List[str]:
        def backtrack(index, current, is_prev_digit):
            """
            回溯生成所有可能的缩写
            
            Args:
                index: 当前处理的字符位置
                current: 当前构建的缩写字符串
                is_prev_digit: 上一个位置是否为数字
            """
            # 终止条件：处理完所有字符
            if index == len(word):
                result.append(current)
                return
            
            # 选择1：保留当前字符
            backtrack(index + 1, current + word[index], False)
            
            # 选择2：将当前字符作为数字的一部分
            if not is_prev_digit:  # 上一个位置不是数字，可以开始新的数字
                # 尝试从当前位置开始的所有可能的数字长度
                for length in range(1, len(word) - index + 1):
                    backtrack(index + length, current + str(length), True)
        
        result = []
        backtrack(0, "", False)
        return result

思路 1：复杂度分析

时间复杂度： $O(2^n \times n)$ ，其中 $n$ 是字符串长度。每个位置有 2 种选择，总共有 $2^n$ 种可能的组合，每种组合需要 $O(n)$ 时间构建字符串。
空间复杂度： $O(2^n \times n)$ ，需要存储所有可能的缩写结果，每个结果长度为 $O(n)$ ，总共有 $2^n$ 个结果。