arrays - 算法 - 检查字符串数组中的任何字符串是否是同一数组中任何其他字符串的前缀

Question

我想检查字符串数组中的任何字符串是否是同一数组中任何其他字符串的前缀。我正在考虑基数排序，然后单遍遍历数组。

谁有更好的主意？

Answer 1

我认为，基数排序可以修改为动态检索前缀。我们所要做的就是按首字母对行进行排序，并在每个单元格中存储没有首字母的副本。然后，如果单元格包含空行，则该行对应于前缀。如果单元格仅包含一个条目，那么当然其中不可能有线路前缀。

这里，这可能比我的英语更干净:

lines = [
"qwerty",
"qwe",
"asddsa",
"zxcvb",
"zxcvbn",
"zxcvbnm"
]

line_lines = [(line, line) for line in lines]

def find_sub(line_lines):
    cells = [ [] for i in range(26)]
    for (ine, line) in line_lines:
        if ine == "":
            print line
        else:
            index = ord(ine[0]) - ord('a')
            cells[index] += [( ine[1:], line )]
    for cell in cells:
        if len(cell) > 1:
            find_sub( cell )

find_sub(line_lines)