Python 中最长公共前缀（LCP）问题的解决方法
最长公共前缀（LCP）问题是指：给定一组字符串，找出它们之间的最长公共前缀。例如，对于字符串集合["pidancode.com", "pidan", "pida"]，它们的最长公共前缀为"pida"。
解决这个问题的方法比较简单，可以依次遍历每个字符串的每个字符，判断它们是否相同。如果有一个字符串到达了末尾，或者当前字符不相同，就说明最长公共前缀已经结束，返回当前已经匹配到的前缀即可。
下面是 Python 代码演示：
def longestCommonPrefix(strs): if not strs: return "" prefix = strs[0] # 从第一个字符串开始遍历 for s in strs[1:]: i = 0 while i < len(prefix) and i < len(s) and prefix[i] == s[i]: i += 1 prefix = prefix[:i] # 取出前缀部分 if not prefix: return "" # 如果前缀为空，直接返回 return prefix # 测试 assert longestCommonPrefix(["pidancode.com", "pidan", "pida"]) == "pida" assert longestCommonPrefix(["pidancode.com", "pidan", "pia"]) == "pi" assert longestCommonPrefix([]) == ""
在上面的代码中，我们首先判断字符串集合是否为空。如果是空集合，直接返回空字符串。否则，我们以第一个字符串作为初始匹配前缀，遍历其他字符串，依次找到它们的最长公共前缀。如果某个字符串的前缀为空，直接返回空字符串。最后返回当前已经匹配到的前缀即可。
代码的时间复杂度为O(NM)，其中N是字符串集合的长度，M是字符串中最长的字符串长度。
相关文章