leetcode 最长公共前缀，代码运行问题

Question

leetcode上有一道最长公共前缀的问题，想换一种方式解，然而打出来的是：flflflo为何print会出来3个结果？ class Solution: def inter_prefix(self,strs=list,minPrefix=str): if minPrefix == '': return minPrefix for i in range(len(strs)): mi = strs[i][:len(minPrefix)] if minPrefix != mi: minPrefix = minPrefix[:-1] self.inter_prefix(strs, minPrefix) print(minPrefix) def longestCommonPrefix(self, strs): """ :type strs: List[str] :rtype: str """ if not strs: return '' minPrefix = strs[0] # if len(strs) == 1:return (minPrefix) for i in range(len(strs)): if len(minPrefix) > len(strs[i]): minPrefix = strs[i] self.inter_prefix(strs,minPrefix) if name == '__main__': Solution().longestCommonPrefix(["flower","flow","flight"])

Answer 1

因为你使用了递归，函数返回的时候由内向外print。

总结下你的思路可以这样写。

def longest_common_prefix(strs):
    if not strs:
        return ''
    # 先选出一个最短字符串作为前缀
    prefix = min(strs, key=lambda s:len(s))
    while True:
        for i in strs:
            # 如果存在前缀不满足的字符串，则前缀缩减一个尾字符，且重新开始循环判断
            if not i.startswith(prefix):
                prefix = prefix[:-1]
                break
        # 如果都满足则跳出while循环
        else:
            break
    return prefix