python最长公共前缀
时间: 2023-10-13 17:29:21 浏览: 71
可以使用以下代码来实现:
```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中可以使用多种方法来找到字符串列表的最长公共前缀。以下是其中的一种常见方法:
```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`作为参数,并返回列表中所有字符串的最长公共前缀。如果列表为空,将返回空字符串。函数首先找到列表中长度最短的字符串,然后遍历该字符串的每个字符,与其他字符串的对应位置字符进行比较。如果有任何不匹配的字符,就直接返回当前位置之前的子串作为最长公共前缀。如果所有字符都匹配,则返回最短字符串本身作为最长公共前缀。
示例用法:
```python
str_list = ['flower', 'flow', 'flight']
prefix = longest_common_prefix(str_list)
print(prefix) # 输出: 'fl'
```
在这个例子中,字符串列表`str_list`的最长公共前缀为'fl'。
python最长公共子序列lcs
Python中最长公共子序列(LCS)问题是求两个字符串最长公共子序列的问题。最长公共子序列是指两个字符串中都存在的最长的子序列(不要求连续)。解法是使用动态规划,用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长的1的序列,其对应的位置就是最长匹配子序列的位置。
下面是一个Python实现的例子:
```python
def lcs(str1, str2):
m = len(str1)
n = len(str2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if str1[i - 1] == str2[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], dp
str1 = "abcba"
str2 = "bdcaba"
length, dp = lcs(str1, str2)
print("最长公共子序列长度为:", length)
print("dp表为:", dp)
```
运行结果:
```
最长公共子序列长度为: 4
dp表为: [[0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 1, 1, 1, 1], [0, 0, 1, 1, 1, 2, 2], [0, 0, 1, 2, 2, 2, 2], [0, 1, 1, 2, 2, 2, 3], [0, 1, 2, 2, 3, 3, 3], [0, 1, 2, 2, 3, 3, 4]]
最长公共子序列为: bcba
```
阅读全文