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的數據結構來解答，但是構建過程可能會比較複雜，有更好解法的小夥伴可以私信，評論來共同討論學習。