Mickey's Blog ·

【leetCode】最长的前缀

这道题呢难度是简单,我们做了这么多费劲的看见这种题目真的是毛毛雨呀,首先来看题

无标题.png

加入我们有

aaab

aaac

aaad

那么他们最长的前缀是什么,大声告诉我

肯定是aaa啊。

那好我们开始编写算法,这里wo我使用了一个小技巧,尽量的让算法少跑,如果两个串的公共前缀只重合三位,那么之后就算重合的再多,也最多只有三位了,也就是说这个前缀肯定是越到最后越短,我们先编写一个工具函数,函数输入两个串,给出重合部分,然后我们先对前两个调用,之后看前两字符串的前缀能不能通用,能通用就返回,不能通用就截短,截多少呢,还是用之前的工具函数。那么算法就写好啦

无标题.png

我看了一下速度还行,最快是82ms,这个也就119.可能是因为我这个判断命中了比较尴尬的情况,如果第一个串能直接适用到最后的话,肯定是我的快