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

15、最长公共前缀子串

题目

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

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

示例1：

示例2：

思路

1、并行扫描法

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

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

2、改进版

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

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

代码

python实现