python求解两个字符串最长公共前缀，从键盘输入

您好，欢迎和 ChitGPT 进行对话！关于您的问题，可以使用 Python 的字符串操作来求解两个字符串的最长公共前缀。以下是一个简单的实现：

str1 = input("请输入字符串1：")
str2 = input("请输入字符串2：")

# 求解最长公共前缀
i = 0
while i < len(str1) and i < len(str2) and str1[i] == str2[i]:
    i += 1

# 输出结果
print("最长公共前缀为：", str1[:i])

这段代码会先从键盘输入两个字符串，然后在一个 while 循环中逐个比较两个字符串的字符。只要字符相同，就继续往后比较，直到出现不同的字符或者某个字符串结束。最后，程序会输出两个字符串的最长公共前缀。

相关问题

任意输入两个字符串，找出它们的最长公共前缀，如their和they的最长公共前缀是the

好的，针对你的问题，可以使用以下算法来求解最长公共前缀：

1. 首先判断输入的字符串是否为空，如果为空则直接返回空字符串。

2. 取第一个字符串作为基准字符串，从第二个字符串开始依次比较每个字符，如果字符相同则继续比较下一个字符，如果字符不同则返回当前已经比较的字符作为最长公共前缀。

3. 如果所有字符串都比较完毕还没有返回，则返回基准字符串作为最长公共前缀。

下面是使用 Python 代码实现上述算法：

def longest_common_prefix(strs):
    if not strs:
        return ""

    for i in range(len(strs[0])):
        for s in strs[1:]:
            if i >= len(s) or s[i] != strs[0][i]:
                return strs[0][:i]
    return strs[0]

使用该函数可以找到任意两个字符串的最长公共前缀，示例如下：

>>> longest_common_prefix(["their", "they"])
'the'
>>> longest_common_prefix(["hello", "world"])
''

用二分查找求字符串数组最长公共前缀

可以用二分查找来求解字符串数组中的最长公共前缀。具体思路如下：

1. 先找到字符串数组中长度最短的字符串，这个字符串的长度就是最长公共前缀的上限。

2. 用二分查找的方式，不断缩小最长公共前缀的上限，直到找到最长公共前缀为止。

具体实现可以参考以下代码：

def longestCommonPrefix(strs):
    if not strs:
        return ""
    min_len = min(map(len, strs))
    left, right = 0, min_len
    while left < right:
        mid = (left + right + 1) // 2
        prefix = strs[0][:mid]
        if all(s.startswith(prefix) for s in strs):
            left = mid
        else:
            right = mid - 1
    return strs[0][:left]

其中，`left` 和 `right` 分别表示最长公共前缀的下限和上限，初始化为 0 和最短字符串的长度。在二分查找的过程中，取中间位置 `mid`，并判断字符串数组中是否所有字符串都以长度为 `mid` 的前缀开头。如果是，说明最长公共前缀的长度可以增加，将 `left` 更新为 `mid`；否则，最长公共前缀的长度需要缩小，将 `right` 更新为 `mid - 1`。最后返回第一个字符串的前 `left` 个字符即可。