python 最长公共前缀 5种解法

编程小白狼

发布于 2024-12-31 00:12:26

19300

代码可运行

文章被收录于专栏：编程小白狼编程小白狼

运行总次数：0

代码可运行

解法一：水平扫描这是最简单的一种方法，逐个字符比较每个字符串的相应位置，直到遇到不匹配的字符为止。

def longest_common_prefix(strs):
    if not strs:
        return ""
    prefix = strs[0]
    for i in range(1, len(strs)):
        while strs[i].find(prefix) != 0:
            prefix = prefix[:-1]
            if not prefix:
                return ""
    return prefix

解法二：垂直扫描在解法一中，我们对每个字符串进行了多次查找操作。为了优化性能，可以将查找操作转换为比较每个字符串的相同索引位置的字符。

def longest_common_prefix(strs):
    if not strs:
        return ""
    for i in range(len(strs[0])):
        char = strs[0][i]
        for string in strs[1:]:
            if i >= len(string) or string[i] != char:
                return strs[0][:i]
    return strs[0]

解法三：分治法将问题分解为更小的子问题，然后递归求解。将字符串数组拆分为两半，分别找出左半部分和右半部分的最长公共前缀，再将两者的最长公共前缀合并。

def longest_common_prefix(strs):
    if not strs:
        return ""
    return divide_conquer(strs, 0, len(strs) - 1)

def divide_conquer(strs, left, right):
    if left == right:
        return strs[left]
    else:
        mid = (left + right) // 2
        lcp_left = divide_conquer(strs, left, mid)
        lcp_right = divide_conquer(strs, mid + 1, right)
        return common_prefix(lcp_left, lcp_right)

def common_prefix(left, right):
    min_len = min(len(left), len(right))
    for i in range(min_len):
        if left[i] != right[i]:
            return left[:i]
    return left[:min_len]

解法四：二分查找将问题转化为寻找最短字符串的最长公共前缀。通过二分查找的方式，每次找到中间长度，判断最短字符串的前半部分是否为所有字符串的公共前缀，如果是，则最长公共前缀一定在后半部分，否则在前半部分。

def longest_common_prefix(strs):
    if not strs:
        return ""
    min_len = min(len(string) for string in strs)
    low, high = 0, min_len
    while low < high:
        mid = (low + high + 1) // 2
        if is_common_prefix(strs, mid):
            low = mid
        else:
            high = mid - 1
    return strs[0][:low]

def is_common_prefix(strs, length):
    prefix = strs[0][:length]
    for string in strs:
        if not string.startswith(prefix):
            return False
    return True

解法五：字典树（Trie）使用字典树存储字符串，从根节点开始遍历，直到找到第一个非公共前缀的节点，返回路径上的字符串。

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

def longest_common_prefix(strs):
    if not strs:
        return ""
    root = TrieNode()
    for string in strs:
        node = root
        for char in string:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True
    prefix = ""
    while root and not root.is_end:
        if len(root.children) == 1:
            char, child = root.children.popitem()
            prefix += char
            root = child
        else:
            break
    return prefix