在Python中查找单词数组中最长前缀序列的长度

在字符串处理中，有时需要查找多个字符串的最长共同前缀，以进行相应的处理。下面介绍一种基于Python的实现方法。

方法一

一种最直观的实现方法是，将单词数组中的第一个单词作为“参照”字符串，然后逐个比较后面的单词中与参照字符串相同的前缀长度，更新最终的最长前缀长度。

def longestCommonPrefix(strs):
    if not strs:
        return ''
    prefix = strs[0]
    for s in strs[1:]:
        while s[:len(prefix)] != prefix:
            prefix = prefix[:len(prefix)-1]
            if not prefix:
                return ''
    return prefix

下面是对该方法的一些说明：

若单词数组为空，则无法获取最长前缀，返回空字符串；
首先将参照字符串设置为单词数组的第一个单词；
遍历单词数组中的其他单词，依次比较其和参照字符串的共同前缀长度；
若当前单词与参照字符串不共有前缀，则更新参照字符串的长度，直到找到共有前缀；
若最终参照字符串长度为0，则说明不存在共同前缀，返回空字符串；
返回更新后的参照字符串，即最长共同前缀。

这种方法时间复杂度为O(nm)，其中n为数组长度，m为最长前缀长度。

方法二

另外一种实现方法是，将单词数组中的所有单词都添加到一个特殊的“字典树”中，然后查找这个字典树的深度。字典树是一种树形数据结构，它表示了一组字符串集合中的前缀关系。

class TrieNode:
    def __init__(self):
        self.children = {}
        self.isEndOfWord = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.isEndOfWord = True

    def depth(self):
        node = self.root
        depth = 0
        while len(node.children)==1 and not node.isEndOfWord:
            node = next(iter(node.children.values()))
            depth += 1
        return depth

def longestCommonPrefix(strs):
    if not strs:
        return ''
    trie = Trie()
    for s in strs:
        trie.insert(s)
    return strs[0][:trie.depth()]

下面是对该方法的一些说明：