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

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) 

Answer 2

如果对它们进行排序，则只需检查每个字符串是否为下一个字符串的前缀。

Answer 3

要接近实现的时间复杂度为O（N ）：计算哈希值每串。

拿出一个好的哈希函数看起来像：

• 从[AZ]映射 - > [1,26]
• 模操作（使用一个大素数），以防止溢出整数的

因此，像 “AB” 被计算为 “12”= 1 * 27 + 2 = 29

甲一点要注意：

要小心你计算散列值的基数。例如，如果基数小于27，可以有两个字符串给出相同的散列值，我们不希望这样。

步骤：

1. 每串
2. 比较当前字符串与其他字符串的哈希值计算哈希值：我会让你找出你会怎么做，comparison.Once两个字符串匹配，你仍然不确定它是否真的是一个前缀（由于我们所做的模操作），所以做一个额外的检查，看看它们是否是前缀。
3. 报告回答