我如何从python中的一组单词中寻找最短的唯一子序列？

Question

如果我有一组类似的单词，例如：

\bigoplus
\bigotimes
\bigskip
\bigsqcup
\biguplus
\bigvee
\bigwedge
...
\zebra
\zeta 

我想找到最短的唯一字母集合，这些字母可以唯一地描述每个单词，即

\bigop:
     \bigoplus
\bigot:
     \bigotimes
\bigsk:
     \bigskip

编辑：请注意，唯一序列标识符始终从单词的开头开始。我编写了一个在输入时提供摘要建议的应用程序。因此，通常用户会从单词的开头开始输入

依此类推，序列仅需足够长即可唯一地描述一个单词。编辑：但是需要从单词的开头开始。表征总是从单词的开头开始。我的想法是：我当时正在考虑对单词进行排序，并根据第一个字母字母进行分组，然后可能使用最长的公共子序列算法来找到最长的公共子序列，并取其长度，并对该唯一的子字符串使用length + 1个字符，但由于我知道最长子序列的算法通常一次只能使用两个参数，因此陷入了困境，而且我每个组中可能有两个以上的单词，以一个特定的字母开头。我要解决已经解决的问题吗？谷歌没有帮助。

Answer 1

我假设您想找到唯一标识字符串的前缀，因为如果您可以选择任何子序列，那么例如om就足以在示例中标识\ bigotimes。

您可以利用以下事实：对于给定的单词，具有最长公共前缀的单词将按照字典顺序与该单词相邻。由于您的字典似乎已经被排序了，因此您可以通过找到最长的前缀来找出每个单词与相邻单词的歧义，从而找出每个单词的解决方案。

例：

>>> lst = r"""
... \bigoplus
... \bigotimes
... \bigskip
... \bigsqcup
... \biguplus
... \bigvee
... \bigwedge
... """.split()
>>> lst.sort()      # necessary if lst is not already sorted
>>> lst = [""] + lst + [""]
>>> def cp(x): return len(os.path.commonprefix(x))
... 
>>> { lst[i]: 1 + max(cp(lst[i-1:i+1]), cp(lst[i:i+2])) for i in range(1,len(lst)-1) }
{'\\bigvee': 5, 
 '\\bigsqcup': 6, 
 '\\biguplus': 5, 
 '\\bigwedge': 5, 
 '\\bigotimes': 6, 
 '\\bigoplus': 6, 
 '\\bigskip': 6}

数字表示单词的最小唯一标识前缀有多长时间。