python最长公共前缀

可以使用以下代码来实现：

def longest_common_prefix(strs):
    if not strs:
        return ""
    
    # 找到字符串中最短的字符串长度
    min_len = min(len(s) for s in strs)
    
    # 依次比较每个字符串的每个字符是否相等
    for i in range(min_len):
        c = strs[0][i]
        if any(s[i] != c for s in strs):
            return strs[0][:i]
    
    return strs[0][:min_len]

这个函数接收一个字符串列表作为参数，然后返回这些字符串的最长公共前缀。它首先找到这些字符串中最短的那个字符串的长度，然后依次比较每个字符串的每个字符是否相等，当有一个字符不相等时，就返回前面的字符子串。如果所有字符串的前缀都相等，就返回最短的那个字符串。

相关问题

python 最长公共前缀

Python中可以使用多种方法来找到字符串列表的最长公共前缀。以下是其中的一种常见方法：

def longest_common_prefix(strs):
    if not strs:
        return ""
    shortest_str = min(strs, key=len)
    for i, char in enumerate(shortest_str):
        for other in strs:
            if other[i] != char:
                return shortest_str[:i]
    return shortest_str

这个函数将接受一个字符串列表`strs`作为参数，并返回列表中所有字符串的最长公共前缀。如果列表为空，将返回空字符串。函数首先找到列表中长度最短的字符串，然后遍历该字符串的每个字符，与其他字符串的对应位置字符进行比较。如果有任何不匹配的字符，就直接返回当前位置之前的子串作为最长公共前缀。如果所有字符都匹配，则返回最短字符串本身作为最长公共前缀。

示例用法：

str_list = ['flower', 'flow', 'flight']
prefix = longest_common_prefix(str_list)
print(prefix)  # 输出: 'fl'

在这个例子中，字符串列表`str_list`的最长公共前缀为'fl'。

python 最长公共子序列

Python 中最长公共子序列（Longest Common Subsequence, LCS）是指两个或多个序列中最长的共同部分，但这些序列可以有不同的排列。计算 LCS 的目的是找出最相似的部分，常用于比较字符串、DNA 序列等。

Python 提供了动态规划算法来解决这个问题，常见的库如 `itertools` 或者编写自定义函数。动态规划的思想是将问题分解成更小的子问题，并存储中间结果以避免重复计算。下面是一个简单的 Python 动态规划实现 LCM 的例子：

from typing import List

def lcs(X: str, Y: str) -> int:
    m = len(X)
    n = len(Y)

    # 创建一个二维数组来存储中间结果
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # 遍历矩阵并填充值
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]

# 示例
X = "ABCDGH"
Y = "AEDFHR"

print("Length of LCS is", lcs(X, Y))