目標：
這題主要目的在於練習常見的字串比對處理。

原題：

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:
Input: ["flower","flow","flight"]
Output: "fl"

Example 2:
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:

class Solution {
    public String longestCommonPrefix(String[] strs) {        
        if (strs == null || strs.length == 0) return "";
        String pre = strs[0];
        int i = 1;
        while (i < strs.length){
            while (strs[i].indexOf(pre) != 0)
                pre = pre.substring(0, pre.length() - 1);
            i++;
        }
        return pre;
    }
}

留意這當中我們使用了String.indexOf()來檢查，
我們只想要pre在剛好0的位置，所以不論這個值是>0(表示出現在中間)
或<0(根本沒出現)，都代表pre需要被調整。
實測上這個解是當前LeetCode上對test cases跑最快的版本(0 ms)。
如果是Python的話，會有比較有趣的解法。
Python支援的min()和max()可以讓我們在List[str]中列出依字母排列順序
最小和最大的字串。當我們可以很簡單拿到這個值時，
我們可以換一個思路，從頭到尾比較的時候，
我們其實只需比最小和最大的兩個字串就好，當它們是相同字元時則往下繼續，
否則就回傳至目前為止的substring。
(因為排序最大和排序最小在某個index字元相同時，
即代表著中間其他字串在此index字元亦相同)

Python:

class Solution:
    def longestCommonPrefix(self, strs: 'List[str]') -> 'str':
        if not strs: return ""
        s1 = min(strs)
        s2 = max(strs)
        
        for i, c in enumerate(s1):
            if c != s2[i]:
                return s1[:i]
        return s1        

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

下篇預告：
0015. 3Sum (Medium)