算法:78.最长公共前缀

https://www.lintcode.com/problem/longest-common-prefix/description

描述

给k个字符串,求出他们的最长公共前缀(LCP)。

样例

在 "ABCD" "ABEF" 和 "ACEF" 中, LCP 为 "A"

在"ABCDEFG", "ABCEFG", "ABCEFA" 中, LCP 为 "ABC"

思路

想法很简单,首先最大前缀的长度是不超过最短字符串的长度。初始化最大前缀长度为最短字符串长度,然后倒序遍历字符串的字符,与其他字符串相同位置的字符进行比较,如果不相同,则将比较位置前移。如果全部相同则返回这时候的长度。

代码

版本1的代码:

上面的代码能通过测试,但其实却存在Bug。能看出问题吗?

改正后代码如下:

小结

版本一的代码存在Bug,比如输入["ABCF","ABEF","ACEF"],应该返回“A”,但是却返回了“ABCF”。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180705G1R3WT00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券