难度: Medium
Submission
运行时间: 44 ms
内存: 19.6 MB
class Solution:
def generateAbbreviations(self, word: str) -> List[str]:
self.res = []
self.word = word
self.dfs(0,0, "")
return self.res
def dfs(self, index, k, ans):
if index == len(self.word):
if k > 0:
ans = ans + str(k)
self.res.append(ans)
return
# 回溯
# 一共有2个候选项：保留第index个字符，缩写第index个字符
# 1. 缩写
self.dfs(index+1, k+1, ans)
# 2. 保留 不缩写
if k > 0:
ans = ans + str(k)
ans = ans + self.word[index]
self.dfs(index+1, 0, ans)
Explain
该题解采用回溯法来列举单词的全部缩写。从单词的第一个字符开始，每一步有两个选择：要么将当前字符保留，要么将其缩写成一个数字。通过递归地探索所有可能的选择组合，最终得到单词的所有缩写形式。具体来说，使用 dfs 函数进行递归，index 表示当前处理的字符位置，k 表示当前已经连续缩写的字符数量，ans 表示当前的缩写字符串。在每一步，优先考虑缩写当前字符，递归处理下一个字符；然后再考虑保留当前字符，将累计的缩写数量（若大于0）添加到 ans 中，并将当前字符也添加到 ans 中，递归处理下一个字符。
时间复杂度: O(2^n)
空间复杂度: O(n * 2^n)
class Solution:
def generateAbbreviations(self, word: str) -> List[str]:
self.res = []
self.word = word
self.dfs(0, 0, "")
return self.res
def dfs(self, index, k, ans):
# 递归边界：已处理完整个单词
if index == len(self.word):
# 将累计的缩写数量添加到结果中
if k > 0:
ans = ans + str(k)
self.res.append(ans)
return
# 回溯
# 一共有2个候选项：保留第index个字符，缩写第index个字符
# 1. 缩写
self.dfs(index+1, k+1, ans)
# 2. 保留 不缩写
# 先将累计的缩写数量添加到ans中
if k > 0:
ans = ans + str(k)
# 再将当前字符添加到ans中
ans = ans + self.word[index]
self.dfs(index+1, 0, ans)
Explore
在回溯法中，选择先缩写当前字符还是先保留当前字符，这主要是算法设计者的选择，并不影响最终结果的完整性，只影响结果的顺序。无论先进行哪种操作，最终生成的缩写集合都应该是相同的，因为算法最终遍历了所有可能的缩写方式。选择先缩写可能是为了在代码实现上保持一致性和简洁性。
在生成缩写时，即使单词中包含重复字符如'aa'，算法也会按照每一个字符独立处理的方式来进行。对于重复字符，算法仍然会探索所有可能的缩写方式（例如，'aa'可以缩写为'2', '1a', 'a1'），这确保了算法的通用性和完整性。尽管如此，这种方式可能会导致一定程度的冗余计算，因为不同的递归路径可能会探索到重复的结果。但在这种情况下，由于算法需要枚举所有可能的缩写组合，这种冗余是必要的。
这种方法可以很好地处理所有边界情况。当单词长度为0时，递归函数在第一次调用时就会满足条件index等于单词长度，因此会直接将累计的缩写数量（若有）添加到ans中，并将结果添加到结果集中。如果单词长度为0且k为0，这意味着没有字符可以缩写，结果集将包含一个空字符串，代表没有缩写。当k为0时，代表累计的缩写数量为0，这种情况下不会向ans中添加数字，而是直接使用当前的ans。因此，算法能够正确处理这些边界情况。
题解中的dfs函数确实是采用深度优先搜索的策略。在处理非常长的单词时，由于每一层递归都对应于单词中的一个字符，因此递归的深度将等于单词的长度。如果单词长度非常大，这可能会导致大量的递归调用，从而影响算法的效率，并可能导致栈溢出错误。在实际应用中，可以通过增加系统的栈大小或使用迭代的方法代替递归来缓解这种情况。