Python 求问一道算法题，最长公共前缀

测试新人 · 2023年11月09日 · 最后由 nine9sky 回复于 2024年01月28日 · 6769 次阅读

题目：https://leetcode.cn/problems/longest-common-prefix/description/?envType=study-plan-v2&envId=top-interview-150

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:


        if not strs: return ""
        str0 = min(strs)
        str1 = max(strs)
        for i in range(len(str0)):
            if str0[i] != str1[i]:
                return str0[:i]
        return str0

求问为什么这种写法可以通过？

看作者的想法好像是想找出最长和最短的两个字符，通过找到是否存在公前缀的骚方法去判断全部字符，不过这种解法会存在一个漏洞就是当 strs=["flower","flow","flight"],找出来的最长会是 flower。而且找最长和最短字符应该是这样写 “min(strs,key=len)”，直接 min 和 max 比较的是字符对应的 ASCII 码。

但是目前很骚的是，这样写居然通过了全部测试，当用例是 strs=["flower","flow","flight"] 时，min(strs) 是等于 “flight” 避开了这个用例，，，，，，看不懂。求下大佬解释下这解法的意思，看晕了

共收到 17 条回复时间点赞

今晚打老虎 #1 · 2023年11月09日

可以转化拿下 ascii 码看看三个字符的顺序，ASCII 码的比对是依次进行的，最小的前缀必然是所有用例共有的，只是在某个点位的字符小于其他用例的该点位字符，在循环获取到该位置后即可进行截取了

测试新人 #2 · 2023年11月09日 Author

对

今晚打老虎回复

那他这里的 min 和 max 目的是什么

今晚打老虎 #3 · 2023年11月09日

就是为了取出最大最小值啊
最大是拥有最长共有前缀或者异位处最靠后的
最小是拥有最短共有前缀 and 异位处最靠前的

disable #4 · 2023年11月09日

费脑子不喜欢动脑子，不刷算法，点点点就完事了

测试新人 #5 · 2023年11月09日 Author

对

今晚打老虎回复

但是这里它是取出 ASCII 码最大和最小的字符，感觉没啥关联呀

今晚打老虎 #6 · 2023年11月09日

对

测试新人回复

你去了解下 ASCII 码就知道了，最长公共前缀必然是由最小字符来决定的，当第 N 位字符是非公共时，[:N] 位前缀必然是最小字符也拥有的，而 “最小” 也意味着 “最长”，你能读懂的话就懂了，不懂的话就去转换下 strs=["flower","flow","flight"] 看看他们的 ASCII 码是怎样的

7楼已删除