Leetcode 14: Longest Common Prefix

问题描述：

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: ["flower","flow","flight"]Output: "fl"

Example 2:

Input: ["dog","racecar","car"]Output: ""Explanation: There is no common prefix among the input strings.

解决方案：

Solution : 可以从一个点开始，

1.最长公共前缀是值 两个字符串中，从第1一个字符开始，从左往右，依次相同的最长公共自字符串，统称为LCP.

2.常规解法是从字符串数组的第一个字符串S1开始，依次和S2比较得到LCP，然后用这个LCP和S3比较，得到新的LCP，依次比较直到字符串数组结束。 时间复杂度为O(N*M),M为最短的字符串长度。

但是我们想加快处理速度，所以可以考虑一个二分拆分比较的方法，也就是分治法，时间复杂度可以降到 O(MlogN),代码如下：

总结：

这题也可以额考虑用Trie的数据结构来解答，但是构建过程可能会比较复杂，有更好解法的小伙伴可以私信，评论来共同讨论学习。