随机字符串编码与最小唯一标识生成
题目描述
给你一个字符串列表 words，你需要为每个字符串生成一个最短的唯一标识符。这个标识符是原字符串的一个前缀，且必须满足：在给定的字符串列表中，没有其他字符串以这个前缀开头。
换句话说，对于列表中的每个单词，你要找到它的一个最短前缀，这个前缀能唯一地指代它。你需要返回一个列表，其中每个元素是对应单词的最短唯一前缀。
示例 1:
输入: words = ["apple", "app", "apricot", "banana"]
输出: ["appl", "app", "apr", "b"]
解释:
- "apple" 的前缀 "a", "ap", "app" 都无法唯一标识它（"app" 也是 "app" 的前缀，"ap" 是多个单词的前缀）。最短唯一前缀是 "appl"。
- "app" 的前缀 "a", "ap" 都不行，"app" 可以唯一标识它。
- "apricot" 的前缀 "a", "ap" 都不行，"apr" 可以。
- "banana" 的前缀 "b" 已经可以唯一标识它。
示例 2:
输入: words = ["dog", "cat", "elephant", "eel"]
输出: ["d", "c", "eleph", "ee"]
要求:
- 你可以假设所有字符串只包含小写字母。
- 你需要高效地处理大量字符串。
解题过程
这个问题本质上是一个前缀查找问题。最直接的思路是：对于每个单词，从第一个字符开始，逐渐增加前缀长度，直到这个前缀在整个列表中唯一。但这样逐个比对效率很低（O(N² * L)，N是单词数，L是平均长度）。
一个更高效的方法是利用哈希表来计数所有可能前缀的出现次数，然后对于每个单词，找到第一个出现次数为1的前缀即可。
步骤1: 理解核心难点
我们要找的是“最短唯一前缀”，关键在于“唯一”。如果我们能快速知道任何一个前缀在所有单词中出现了多少次，问题就简单了：对每个单词，从第一个字符开始，逐个字符增加前缀，查这个前缀的计数，第一次遇到计数为1的前缀就是答案。
难点在于如何高效地“计数所有可能前缀”？一个单词的所有前缀个数是 O(L)，N 个单词就是 O(N*L)。如果全部枚举并计数，是可以的。
步骤2: 前缀计数策略
我们可以用一个哈希表（字典）prefix_count 来记录每个前缀在所有单词中出现的次数。具体做法：
- 遍历每个单词。
- 对于每个单词，生成它的所有可能前缀（从第一个字符到整个单词）。
- 在哈希表中对应前缀的计数加1。
例如 "apple" 的前缀有 "a", "ap", "app", "appl", "apple"，每个计数+1。
这样做完之后，prefix_count["app"] 的值就表示有多少个单词以 "app" 开头。
步骤3: 为每个单词找最短唯一前缀
有了前缀计数的哈希表后，对于每个单词：
- 再次生成它的所有前缀（按从短到长的顺序）。
- 在哈希表中查找该前缀的计数。
- 第一个遇到计数为 1 的前缀，就是该单词的最短唯一前缀。
为什么是计数为1？因为只有这个单词自己有这个前缀，其他单词没有，所以唯一。
步骤4: 举例推导
以示例1 words = ["apple", "app", "apricot", "banana"] 为例：
-
构建前缀计数哈希表：
- "apple" 前缀: "a", "ap", "app", "appl", "apple" → 各+1。
- "app" 前缀: "a", "ap", "app" → 各+1。
- "apricot" 前缀: "a", "ap", "apr", "apri", ... → 各+1。
- "banana" 前缀: "b", "ba", "ban", ... → 各+1。
最终部分前缀计数：
- "a": 3 （apple, app, apricot）
- "ap": 3
- "app": 2 （apple, app）
- "appl": 1 （只有 apple）
- "apr": 1 （只有 apricot）
- "b": 1 （只有 banana）
-
为每个单词找最短唯一前缀：
- "apple"：查 "a"→3，不唯一；"ap"→3，不唯一；"app"→2，不唯一；"appl"→1 ✅ → "appl"。
- "app"：查 "a"→3，不唯一；"ap"→3，不唯一；"app"→2 ❌？等等，"app" 计数是2，不是1，所以不唯一？这里要注意：前缀必须在整个列表中唯一，但 "app" 这个前缀是 "apple" 和 "app" 共有的，所以计数为2，不是唯一。所以 "app" 本身不是唯一前缀？不对，我们是要为单词 "app" 找前缀，"app" 是它自己的完整字符串，它的前缀 "app" 的计数是2，但 "app" 本身作为一个完整的单词，我们需要找的是能唯一标识 "app" 这个单词的前缀，既然 "app" 这个前缀被两个单词共享，那就不能用它，必须用更长的前缀？但 "app" 没有更长的前缀了（它只有3个字符）。仔细看题意：我们要为每个字符串生成一个最短的唯一标识符，这个标识符是原字符串的一个前缀。如果这个单词本身（完整字符串）作为前缀，它的计数是2，说明另一个单词也有此前缀（另一个单词是它的前缀，或者它是另一个单词的前缀）。在示例中，"app" 是 "apple" 的前缀，所以 "app" 这个字符串作为前缀时，计数是2，那么它就不能作为 "app" 的唯一标识符，因为 "apple" 也有此前缀，无法区分。但示例输出是 "app" 啊，为什么？这里的关键是：当我们说“前缀”时，是指从单词开头截取的一部分，但当我们用这个前缀去匹配时，是看列表中是否有其他单词以此前缀开头。如果 "app" 是 "apple" 的前缀，那么 "apple" 确实以 "app" 开头，所以 "app" 这个前缀并不唯一指向 "app" 这个短单词，也指向 "apple"。所以示例输出 "app" 是怎么来的？我检查一下：示例输入
["apple", "app", "apricot", "banana"]，输出是["appl", "app", "apr", "b"]。对于 "app"，它的输出是 "app"，说明他们认为 "app" 是唯一的？但 "apple" 以 "app" 开头，应该不唯一。这里矛盾了。我们重新理解题意：最短唯一前缀的意思是，这个前缀能唯一确定是哪个单词。即，在列表中，没有其他单词 具有这个前缀。如果 "app" 是 "apple" 的前缀，那么 "apple" 也具有此前缀，所以 "app" 不能唯一标识 "app" 这个短单词。但示例却说可以。仔细看："app" 是 "apple" 的前缀，但 "apple" 的完整字符串不是 "app"，而是更长。当我们用 "app" 这个前缀去匹配单词时，匹配规则是：单词以此前缀开头。那么 "apple" 确实以 "app" 开头，所以 "app" 这个前缀能匹配到两个单词："app" 和 "apple"。因此它不是唯一的。示例输出似乎有误？或者我理解错了？
实际验证：在示例中，对于 "app"，如果我们用前缀 "app" 去匹配列表中所有单词，会匹配到 "app" 和 "apple"，所以不是唯一。但题目要求是“没有其他字符串以这个前缀开头”，那么 "app" 这个前缀有其他字符串（"apple"）以它开头，所以不符合。那么 "app" 应该需要更长的前缀，但 "app" 本身只有3个字符，没有更长的前缀了。所以 "app" 的最短唯一前缀应该是 "app" 本身？但 "app" 本身作为完整字符串，它的前缀就是 "app"，但 "apple" 也以 "app" 开头，所以 "app" 这个前缀不是唯一的。这似乎矛盾。我们再看题目描述：“这个标识符是原字符串的一个前缀”，意味着标识符长度可以等于原字符串长度。对于 "app"，如果我们取整个字符串 "app" 作为前缀，那么它是 "app" 的一个前缀（整个字符串也是前缀之一）。然后我们检查列表中是否有其他单词以 "app" 开头："apple" 确实以 "app" 开头，所以 "app" 这个前缀不是唯一的。那么 "app" 就没有唯一前缀了？这显然不对。所以唯一的可能是：前缀匹配时，是精确匹配整个前缀，但只考虑列表中每个单词本身，而不是用前缀去匹配其他单词的开头。不，原文是“没有其他字符串以这个前缀开头”，意思就是其他单词不能以此前缀开头。所以 "app" 确实不符合。但示例输出是 "app"，说明示例的逻辑是：对于 "app"，前缀 "app" 是它的唯一前缀，因为虽然 "apple" 以 "app" 开头，但 "apple" 的长度比 "app" 长，而我们比较时是否只考虑前缀长度小于等于单词长度？不，任何其他单词只要以此前缀开头就不行。所以示例似乎错了？我查一下原始题目（LeetCode 面试题 17.13：恢复空格？不对）。实际上这是经典问题“最短唯一前缀缩写”，通常的解法是：每个单词的最短唯一前缀，是其所有前缀中，在整个单词列表的前缀集合里出现次数为1的最短那个。在示例中，当我们统计前缀出现次数时，对于 "app" 这个前缀，它出现在两个单词中：一个是 "app" 本身的所有前缀中包含 "app"，另一个是 "apple" 的所有前缀中也包含 "app"。所以 "app" 的计数是2，不是1。那么对于单词 "app"，它的前缀 "a" 计数3，"ap" 计数3，"app" 计数2，都没有1，那它就没有最短唯一前缀了？这显然不对。所以这里的关键是：当我们统计前缀出现次数时，每个单词的所有前缀中，是否包含单词本身？是的，包含。那么 "app" 这个前缀会被统计两次（来自 "app" 和 "apple"）。那么 "app" 的所有前缀计数都大于1，无法找到计数为1的。但示例输出是 "app"，说明他们认为 "app" 是唯一的。矛盾在于：如果我们认为 "app" 是 "apple" 的前缀，那么 "app" 就不能唯一标识 "app" 这个短单词。但如果我们换一种理解：最短唯一前缀是指，在列表中，没有其他单词的整个字符串等于这个前缀**？不，题目明确说“以这个前缀开头”。所以示例可能给错了？我查一下类似问题：LeetCode 1081. 最小表示法？不是。实际上这是“最短唯一前缀”问题（Shortest Unique Prefix），常见于字典树（Trie）的例题。在字典树中，我们统计每个节点被多少个单词经过。对于单词 "app"，路径 "a"->"p"->"p"，最后一个节点 "p" 的计数是2（因为 "apple" 也经过前两个 "p"？等等，字典树中每个节点计数是经过该节点的单词数。对于 "app"，构建字典树后，节点 a 计数3，节点 ap 计数3，节点 app 计数2（因为 "app" 和 "apple" 都经过这里）。那么对于单词 "app"，从根节点开始，找到第一个计数为1的节点，那是节点 "appl"（计数1），但 "appl" 不是 "app" 的前缀，因为 "app" 只有3个字符。所以字典树方法中，对于 "app"，它找不到计数为1的节点，那么它的最短唯一前缀就是整个单词 "app"。这是因为字典树中，一个单词的结束节点可能有多个单词经过，但如果一个单词是另一个单词的前缀，那么短单词的最短唯一前缀就是它自己。这正是示例的输出逻辑：对于 "app"，输出 "app"。所以我们的哈希表计数方法需要调整：我们统计的是每个前缀被多少个单词作为前缀（即以此前缀开头）。对于 "app" 这个前缀，有哪些单词以 "app" 开头？有 "app" 和 "apple"，所以计数是2。对于 "apple" 的前缀 "appl"，只有 "apple" 以 "appl" 开头，计数1。所以对于 "app"，它的所有前缀计数都>1，那么它的最短唯一前缀就是它自己（完整字符串）。但完整字符串 "app" 的计数是2（因为 "apple" 也以 "app" 开头），所以还是>1，这说不通。除非我们对“前缀”的定义是：前缀必须是单词的严格前缀（即不能等于单词本身）？不，题目说“是原字符串的一个前缀”，包括整个字符串。所以这个矛盾点在于：如果我们用“以此前缀开头”来计数，那么 "app" 这个字符串作为前缀，会匹配到 "app" 和 "apple"，所以计数2。但当我们为单词 "app" 寻找最短唯一前缀时，我们检查它的前缀 "app"（即整个字符串），计数是2，不唯一。但根据题意，整个字符串一定是唯一的（因为列表中字符串可能重复？题目没说不重复，但通常假设不重复）。如果列表中有重复字符串，那整个字符串也不唯一。但通常假设字符串唯一。在示例中，"app" 和 "apple" 是两个不同的字符串，所以 "app" 这个完整字符串是唯一的标识符（没有其他字符串和它完全相同）。但当我们用前缀匹配时，"apple" 以 "app" 开头，所以 "app" 这个前缀能匹配到两个不同的字符串，因此不是唯一前缀。但唯一标识符应该是能唯一确定一个字符串的，"app" 这个前缀能匹配到两个字符串，所以不能唯一确定是 "app" 还是 "apple"。所以严格来说，"app" 不能作为 "app" 的唯一标识符。但示例输出是 "app"，说明题目可能认为，当我们用前缀标识一个单词时，我们只关心这个前缀是否能唯一对应到这个单词，而不考虑这个前缀是否匹配到其他单词的更长子串？不，题目明确说“没有其他字符串以这个前缀开头”。所以示例可能错了？我搜索记忆，这是 LeetCode 1166. 设计文件系统？不是。实际上这是“最短唯一前缀”问题，通常的解法用字典树，对于 "app"，在字典树中，从根到叶子，每个节点计数为经过的单词数。对于 "app" 路径，节点计数分别为 3,3,2。没有计数为1的节点，所以最短唯一前缀就是整个单词。因为整个单词是唯一的标识。但整个单词 "app" 作为前缀，在字典树中对应节点的计数是2（因为 "apple" 也经过），但当我们说“唯一”时，是指这个前缀只能对应到一个单词，而不是经过的节点数。在字典树中，节点计数表示有多少单词以此节点为前缀路径的一部分。但如果我们用完整路径 "a-p-p" 来标识 "app"，那么它是唯一的，因为虽然 "apple" 也经过前三个节点，但 "apple" 的完整路径更长。所以唯一性判断应该是：对于单词 w 的一个前缀 p，如果没有任何其他单词以 p 开头，则 p 是唯一前缀。在字典树中，我们可以通过检查 p 对应的节点是否只有一个单词经过（即节点计数为1）来判断。对于 "app" 的前缀 "app"，对应节点计数为2，因为有两个单词经过（"app" 和 "apple"），所以不唯一。但为什么示例输出是 "app" 呢？我怀疑示例中 "app" 的输出应该是 "app" 本身，但根据唯一性定义，这不成立。除非题目中“以这个前缀开头”是指“其他单词的完整字符串是否等于这个前缀”？不，是“开头”。所以这可能是一个常见的误解。我决定按照字典树的标准解法来解释，因为哈希表方法会有这个矛盾。
标准解法是用字典树（Trie），每个节点记录经过的单词数量。对于每个单词，从根节点开始，沿着字符向下走，找到第一个计数为1的节点，从根到该节点的路径就是最短唯一前缀。如果走完整个单词都没有计数为1的节点，那么最短唯一前缀就是整个单词。
在示例中，构建字典树后：
- "apple" 路径：a(3), ap(3), app(2), appl(1) → 找到计数1的节点是 "appl"，所以前缀是 "appl"。
- "app" 路径：a(3), ap(3), app(2) → 没有计数1的节点，所以前缀是整个单词 "app"。
- "apricot" 路径：a(3), ap(3), apr(1) → 找到 "apr"。
- "banana" 路径：b(1) → 找到 "b"。
这与示例输出一致。所以我们的哈希表方法需要模仿字典树的行为：我们统计每个前缀被多少个单词作为前缀（即以此前缀开头），但当我们为单词 w 寻找最短唯一前缀时，我们看 w 的每个前缀 p，如果前缀 p 的计数为1，则 p 是唯一的。这里“计数为1”表示只有 w 以 p 开头。但注意，对于 "app"，它的前缀 "app" 的计数是2（因为 "apple" 也以 "app" 开头），所以不唯一。但为什么输出是 "app"？因为当 w 的所有前缀计数都大于1时，说明 w 是其他某个单词的前缀，那么 w 的完整字符串本身是唯一能标识它的，因为其他更长的单词虽然以 w 开头，但 w 作为完整字符串，与其他单词的完整字符串不同。但根据定义，完整字符串 w 也是 w 的一个前缀，且 w 的计数是2（因为 "apple" 也以 w 开头），所以不唯一。这里就出现了矛盾。所以严格来说，哈希表方法不能直接通过计数为1来判断，需要额外处理：如果单词 w 的所有前缀计数都大于1，则最短唯一前缀就是 w 本身。但 w 本身作为前缀的计数也大于1，所以不合定义。因此，唯一正确的解法是字典树，因为字典树中节点计数表示“有多少单词以此节点为前缀路径的一部分”，但判断唯一性时，我们还需要知道是否有其他单词正好结束于此节点。在字典树中，我们还可以记录结束于该节点的单词数。但标准最短唯一前缀问题通常用字典树，且每个节点计数为经过的单词数，然后对于单词 w，找到第一个计数为1的节点即可。如果走到底都没有计数1，则用整个单词。这正好匹配示例。
所以，我们放弃哈希表方法，改用字典树。
步骤5: 字典树（Trie）解法详解
字典树节点结构：
children: 字典，键为字符，值为子节点。count: 整数，表示经过该节点的单词数量（即有多少单词以此节点对应的前缀为前缀）。
算法步骤：
- 构建字典树：遍历每个单词，将单词插入字典树，对路径上每个节点的
count加1。 - 查询最短唯一前缀：对于每个单词，从根节点开始，沿着字符向下走，同时记录路径字符串。找到第一个
count为1的节点，此时路径字符串即为最短唯一前缀。如果走完整个单词都没有count为1的节点，则整个单词就是最短唯一前缀。
步骤6: 示例推导（字典树）
以 words = ["apple", "app", "apricot", "banana"] 为例：
-
插入 "apple":
- 根节点 count=1
- 节点 'a' count=1
- 节点 'ap' count=1
- 节点 'app' count=1
- 节点 'appl' count=1
- 节点 'apple' count=1
-
插入 "app":
- 根节点 count=2
- 节点 'a' count=2
- 节点 'ap' count=2
- 节点 'app' count=2 （"apple" 已经经过这里，所以加1变成2）
- 节点 'app' 的子节点没有 'p'？不对，"app" 只有三个字符，所以插入到 'a'->'p'->'p'，第三个字符 'p' 对应的节点就是 'app' 节点，count 从1变成2。
-
插入 "apricot":
- 根节点 count=3
- 节点 'a' count=3
- 节点 'ap' count=3
- 节点 'apr' count=1（新节点）
- 后续节点 count 都是1。
-
插入 "banana":
- 根节点 count=4
- 节点 'b' count=1
- 后续节点 count 都是1。
现在字典树节点计数（部分）：
- 根节点: 4
- 'a': 3
- 'ap': 3
- 'app': 2
- 'appl': 1
- 'apple': 1
- 'apr': 1
- ...
- 'b': 1
查询：
- "apple": 路径 'a'(3) -> 'ap'(3) -> 'app'(2) -> 'appl'(1) ✅ → 前缀 "appl"。
- "app": 路径 'a'(3) -> 'ap'(3) -> 'app'(2) 没有 count=1 的节点，走完单词，所以整个单词 "app" 是答案。
- "apricot": 'a'(3) -> 'ap'(3) -> 'apr'(1) ✅ → 前缀 "apr"。
- "banana": 'b'(1) ✅ → 前缀 "b"。
输出：["appl", "app", "apr", "b"]，与示例一致。
步骤7: 复杂度分析
- 构建字典树：O(T)，T 是所有单词的字符总数。
- 查询：O(T)，每个字符访问一次。
- 空间复杂度：O(T)，字典树节点数。
步骤8: 代码实现（Python）
class TrieNode:
def __init__(self):
self.children = {}
self.count = 0
def shortest_unique_prefix(words):
root = TrieNode()
# 插入所有单词，计数
for word in words:
node = root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.count += 1
res = []
for word in words:
prefix = []
node = root
for ch in word:
node = node.children[ch]
prefix.append(ch)
if node.count == 1:
break
res.append(''.join(prefix))
return res
# 测试
words = ["apple", "app", "apricot", "banana"]
print(shortest_unique_prefix(words)) # 输出: ['appl', 'app', 'apr', 'b']
总结
本题的关键是利用字典树（Trie）高效统计所有单词的前缀共享次数，并通过寻找第一个计数为1的节点来得到最短唯一前缀。字典树能自然处理前缀关系，并在线性时间内解决问题，非常适合此类前缀查找场景。