Python 中的最长公共前缀

在本文中，您将学习 Python 中的最长公共前缀。有多种方法可以在 Python 中找到最长公共前缀。但在讨论这些方法之前，您需要了解**最长公共前缀**。

什么是长公共前缀？

对于字符串对 string1 和 string2，作为 string1 和 string2 前缀的最长字符串称为**最长公共前缀 (LCP)**。

一个演示如何在字符串列表中查找最长公共前缀的 Python 代码片段

代码

输出

foo

说明

• 名为**"strs"**的字符串列表是**"longest_common_prefix"**的输入参数
• 首先，我们处理列表为空的**特殊情况**，方法是返回**空字符串**。一组空字符串没有共同的前缀。
• 接下来，我们找到列表中最短字符串的长度。我们将使用此值循环遍历最短字符串中的每个字符，并将其与其他字符串进行比较。
• 之后，我们循环遍历最短字符串中的每个字符，在第一个不匹配处停止。
• 对于每个字符位置**i**，我们检查列表中所有其他字符串在该位置的字符是否与第一个字符串**strs[0]**相同。如果存在不匹配，我们将返回该点之前的字符串。如果存在不匹配，我们将返回到该点的字符串。
• 如果我们遍历整个循环而没有找到不匹配，我们就知道整个最短字符串是公共前缀。

此方法具有**O(N*M) 时间复杂度**，其中**N**是列表中**字符串**的数量，**M**是**最短字符串**的长度。这是因为我们需要循环遍历最短字符串中的每个字符，并且需要将每个字符与列表中的其他字符串进行比较。

使用“zip”函数

在 Python 中查找最长公共前缀的另一种方法是 zip 函数。您可以使用 zip 函数在 Python 中查找最长公共前缀。

代码

输出

foo

说明

• 我们首先处理列表为空的**特殊情况**，这与之前的实现相同。
• 我们使用**zip 函数**按位置对每个字符串的字符进行分组。**zip(*strs)**中的*****用于将字符串列表**解包**为**zip 函数**的单独参数。
• 我们循环遍历每个字符组，检查组中是否有多个不同的字符。
• 如果组中存在多个不同的字符，我们将返回该点之前的字符串。
• 如果我们遍历整个循环而没有找到不匹配，我们就知道整个**最短字符串**是**公共前缀**。我们将返回列表中的**最短字符串**，该字符串保证是公共前缀。

该算法的**时间复杂度**为**O(N*M)**，其中**N**是列表中字符串的数量，**M**是**最短字符串**的长度。然而，在某些情况下，它可能比之前的实现更快，特别是当字符串列表中只有少数不同的字符时。

使用二分查找方法

此方法的基本思想是在公共前缀的长度上执行二分查找，起始范围为**[0, min_len]**，其中**min_len**是列表中最短字符串的长度。在每一步，我们检查长度为 mid 的前缀是否是所有字符串的公共前缀。如果是，我们可以丢弃范围的下半部分，因为我们知道比 mid 短的前缀也是公共前缀。如果不是，我们可以丢弃范围的上半部分，因为我们知道比 mid 长的前缀不可能是公共前缀。

代码

输出

foo

说明

• 我们首先处理列表**为空**的特殊情况，这与之前的实现相同。
• 我们找到列表中**最短字符串**的长度，这与之前的实现相同。
• 我们设置二分查找的初始范围，即**[0, min_len]**。为了记录当前范围，我们使用**left**和**right 变量**。
• 我们进入一个**while 循环**，该循环一直持续到范围缩减到单个值。在每一步，我们都使用整数除法计算范围的中点。我们使用**(left + right + 1) // 2**而不是**(left + right) // 2**来确保中点向上取整而不是向下取整。这是因为我们想返回范围中最后一个元素的值。
• 我们确定**mid 长度的前缀**是否是列表中所有字符串的公共前缀。我们使用带有 all 函数的生成器表达式来做到这一点。如果前缀是公共前缀，我们将范围更新为**[mid, right]**。否则，我们将范围更新为**[left, mid - 1]**。
• 我们继续**循环**直到范围缩减到单个值，该值表示最长公共前缀的长度。
• 最后，我们通过从列表中第一个字符串的切片到计算出的长度来返回最长公共前缀。

该算法的**时间复杂度**为**O(NMlogM)**，其中**N**是列表中字符串的数量，**M**是**最短字符串**的长度。二分查找减少了我们与之前的实现相比需要进行的比较次数，从而得到了一个更快的算法。

使用 Trie（前缀树）方法

在此方法中，我们创建一个**Trie 数据结构**来存储列表中所有字符串的前缀。之后，我们从根遍历**Trie**到具有多个子节点的最高节点。**最长公共前缀**由从根到该**节点的路径表示。mid-1。**

示例

这是 Python 中此方法的示例实现

输出

foo

说明

• 我们定义一个**TrieNode** **类**来表示**Trie**中的节点。每个节点都有一个 children 字典来存储其子节点，以及一个**is_end_of_word**标志来指示节点是否代表单词的结尾。
• 我们定义一个**Trie 类**来表示**Trie 数据结构**。insert 方法通过从根遍历**Trie**并根据需要添加新节点来将单词插入**Trie**。**longest_common_prefix**方法从根遍历**Trie**到具有多个子节点的最高节点，并将从根到该节点的路径作为最长公共前缀返回。
• 我们创建一个新的**Trie 实例**并将列表中的所有字符串插入**Trie**。
• 为了确定最长公共前缀，我们使用**Trie**实例的**longest_common_prefix**方法。
• **longest_common_prefix**方法从**Trie**的根开始，并初始化一个空字符串来表示前缀。之后，它会迭代地遍历**Trie**，直到到达具有多个子节点的最高节点。在每一步，它会检查当前节点是否只有一个子节点且不是单词的结尾。如果是，它会将子节点的键添加到前缀并移动到子节点。如果不是，则最长公共前缀是当前前缀。
• 该算法的**时间复杂度**为**O(NM)**，其中**N**是列表中字符串的数量，**M**是**最长公共前缀**的长度。在最坏的情况下，当所有字符串都有相同的前缀时，**Trie**将有**M 层**，每层最多有**26 个子节点**。因此，Trie 的**空间复杂度**为**O(NM)**。然而，Trie 的实际使用空间可能小于此，具体取决于输入字符串的结构。