给定字符串列表，查找其他字符串中没有出现的每个字符串的最短唯一子字符串
给定字符串列表，查找其他字符串中没有出现的每个字符串的最短唯一子字符串
提问于 2022-05-23 23:27:16
问题是：
给定一个字符串列表，查找每个字符串的最短唯一子字符串，以便该子字符串不会出现在任何其他字符串中。
例如：
Input: ["cheapair", "cheapoair", "peloton", "pelican"]
Output:
"cheapair": "pa" // every other 1-2 length substring overlaps with cheapoair
"cheapoair": "po" // "oa" would also be acceptable
"pelican": "ca" // "li", "ic", or "an" would also be acceptable
"peloton": "t" // this single letter doesn't occur in any other string我认为这是用动态规划解决的，但老实说，我不知道如何做到这一点，除了蛮力:存储每个单词的所有子字符串，并检查它们是否存在于其他任何一个，这是一个糟糕的想法。
回答 1
Stack Overflow用户
发布于 2022-05-24 00:17:14
构建所有子字符串以查找出现在两个(或更多)字符串中的字符串。然后，对每个字符串，打印一个最短的子字符串，不会出现在两个(或更多)中。也许不是最好的(取决于你的数据和你认为什么是“最好的”)，但工作简单。
strings = ["cheapair", "cheapoair", "peloton", "pelican"]
def substrings(s):
n = len(s)
return {s[i:i+k]
for k in range(1, n+1)
for i in range(n-k+1)}
one = set()
two = set()
for s in strings:
subs = substrings(s)
two |= one & subs
one |= subs
for s in strings:
subs = substrings(s)
uniq = subs - two
print(s, min(uniq, key=len))输出(在网上试试！)：
cheapair pa
cheapoair oa
peloton t
pelican anPreliminary 基准测试有一个修改后的版本，按长度进行，就像Nick的一样。拿几袋盐来看这个：( 1)这个问题有一些不明确的问题(我现在在这个问题下问)。( 2)解决方案产生所有有效的子字符串，而不是只生成一个子字符串。3)我修改了Nick的一点，使它在这里工作(没有任何应该影响它的速度)。4)这是一个最坏的情况输入，其中每个字符串都需要最大长度，也就是说，除了它本身没有唯一的子字符串。
0.19 s Kelly2
1.34 s Nick
0.19 s Kelly2
1.35 s Nick
0.19 s Kelly2
1.34 s Nick页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/72358798
复制相关文章
相似问题
腾讯云开发者
