python - 查找 "random"字符串列表中至少 2 个元素上存在的最长前缀

Question

给定一个字符串列表，例如:

myList = ["foo", "foobar", "football", "footbag", "bar"]

查找列表中至少 2 个字符串中存在的最长前缀:

Longest prefix is "footba" present in "football" and "footbag"

该列表将通过输入来填充，并且并非所有输入都具有共同的前缀。

要被视为一个选项，前缀出现在列表中的两个字符串上就足够了。如果有多个选项，则必须返回最长的一个。

在我的研究中，我已经找到了如何获取所有字符串的最长公共(public)前缀，例如:

列表:["foo_a","foo_b","foo_c","fnord"]

输出:Longest common prefix is "f"

但是，我的列表中的字符串可能甚至不以相同的字母开头。

Answer 1

你可以建立一个 prefix trie 的森林s，然后搜索具有两个(非空)子节点的最深节点的“高度”(距离根有多远)。该节点代表最长的公共(public)前缀。

如果您不关心性能，您可以简单地迭代列表中的所有单词，并将每个单词(其前缀)与其余单词进行比较，同时不断更新最大值:

def common_prefix_size(s1, s2):
    res, i = 0, 0
    while i < min(len(s1), len(s2)):
        if s1[i] == s2[i]:
            res += 1
            i += 1
        else:
            break
    return res



def longest_prefix(lst):
    res = ''
    maxsize = 0
    for i in range(len(lst) - 1):
        for j in range(i + 1, len(lst)):
            t = common_prefix_size(lst[i], lst[j])
            maxsize = max(maxsize, t)
            if maxsize == t:
                res = lst[i][:maxsize]
    return res

myList = ["foo", "foobar", "football", "footbag", "bar"]

print(longest_prefix(myList)) # footba