每天一道算法:最长公共前缀子串

15、最长公共前缀子串

题目

实现一个函数,要求找到一系列字符串中的最长公共前缀子串。

如果没有公共前缀,则返回空字符串""。

示例1:

示例2:

思路

1、并行扫描法

从左到右,并行扫描,当某一位置的所有字符都相等时,公共字符串长度+1,继续扫描下一位。

时间复杂度为 O(nl),其中n为字符串个数,l为字符串平均长度。

2、改进版

仍然是从左到右并行扫描,但是这次以最短字符串为基准,只要与最短字符串不相同,则算法结束。

这样做的好处是免去了判断是否溢出和字符相加的过程。

代码

python实现

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

扫码关注云+社区

领取腾讯云代金券