阿聪的小破站algo›frame
前缀树算法详解
最近在刷力扣的时候，有一道题：14. 最长公共前缀， 可以用python3的特殊api来求解，像是用zip函数，将可迭代对象对应的元素打包成一个个元组，然后返回元组组成的列表。我们就可以根据元组的长度来判断是否前缀是否相同。
比如
zip(['flower', 'flow', 'flight'])返回的结果是[('f', 'f', 'f'),('l', 'l', 'l'),('o', 'o', 'i'),('w', 'w', 'g')]
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
ans = zip(*strs) # List[Tuple]
s = ''
for i in ans:
if len(set(i)) == 1:
s += i[0]
else:
break # 后面能匹配上也不要了
return s但是看很多题解都是使用trie树来求解的，这里就来仔细的学习了解一下。 参考labuladong网站文章： 前缀树算法模板秒杀五道算法题