0014. Longest Common Prefix (Easy)

Question

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

1
2

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

Example 2

1
2
3

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

Note:

All given inputs are in lowercase letters a-z.

分析/解題

題目要求從一組字串陣列中找出其最長的共用前綴，
字串只會由a到z所構成，若沒有的話則回傳空字串。

同樣的，若遇到這個問題，請第一時間記得問他們有沒有排序XD
依據資料的分布不同，不同的解法應該會有不同的優勢，
但非特殊情況的話，總體時間複雜度應為: O(單一字串長 * 總字串數)

最直觀的想法，就是從頭開始將每個相同位置的字元比對一次，
相同則往下繼續做，不同則停下將結果輸出，
但這麼做可能前面每次都要掃過相同位置的所有字元。

我們可以換個角度想，若先拿第一個字串當作common prefix(命名作pre)，
接下來用其餘的字串來檢查這個pre是否是其prefix，是的話則檢查下一個，
不是的話就將pre的尾端刪去重新檢查，這樣一旦當中有一個字串有大幅度差異，我們很快就能將pre縮減到很短。

Java

留意這當中我們使用了String.indexOf()來檢查，
我們只想要pre在剛好0的位置，所以不論這個值是>0(表示出現在中間)
或<0(根本沒出現)，都代表pre需要被調整。
實測上這個解是當前LeetCode上對test cases跑最快的版本(0 ms)。

如果是Python的話，會有比較有趣的解法。
Python支援的min()和max()可以讓我們在List[str]中列出依字母排列順序 最小和最大的字串。當我們可以很簡單拿到這個值時，
我們可以換一個思路，從頭到尾比較的時候，我們其實只需比最小和最大的兩個字串就好，當它們是相同字元時則往下繼續，否則就回傳至目前為止的substring。(因為排序最大和排序最小在某個index字元相同時，即代表著中間其他字串在此index字元亦相同)

Python

面試實際可能會遇到的問題

「如果不能用indexOf的話你會怎麼做？」
(可使用String.toCharArray()轉成陣列後再操作)
「如果這組陣列被預期長短差異很大呢？」
(先掃過一遍陣列，拿最短的當pre)
「Best Case和Worst Case的時間複雜度？什麼狀況下會發生？」
(依照你的解法應該有所不同)
「如果加入<0的判斷式的話可以提升這個程式的效率嗎？」
(不一定，因為不保證多快能遇到前綴完全不同的字串 ，
所以端看這組資料是預期很有可能出現結果為空字串，
還是大多數都會有共同前綴來決定。)

從LeetCode學演算法，我們下次見囉，掰~