0014 - Longest Common Prefix

大意說明

找出一組字串陣列中，相同字串的部份。

例如 ["flower","flow","flight"] 的結果是 fl ，["dog","racecar","car"] 的結果是空字串（沒有相同的部份）

解題思路

想不到，所以參考了答案

首先先做字串 list 的排序，原因是字串經過排序之後，一定是由各字串的字母一路排上去，所以最不一樣的肯定在最後面，這樣就可以把比較範圍縮小（也比較不會不知所措）

接著就是第一個字串跟最後一個字串比較，然後用長度最小的字串長度當作迴圈結束條件之一

如果比到一半發現字元不同，直接跳掉。否則就繼續加入字串，直到結束條件達成為止。

程式碼如下：

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """

        result = ""
        
        # 依照字串字母順序排序，最不一樣的一定在最後面
        sorted_list = sorted(strs)
        
        first = sorted_list[0]
        last = sorted_list[-1]

        for i in range(0, min(len(first), len(last))):
            if first[i] != last[i]:
                return result
            result += first[i]
        
        return result

這邊反而鼓勵使用程式語言內建排序方式，Python 的話就是 sorted() ，Java 的話是 Array.sort() 。

以下是 Java code:

class Solution {
    public String longestCommonPrefix(String[] strs) {
        ArrayList<String> arraylist = new ArrayList<>(Arrays.asList(strs));
        arraylist.sort(Comparator.naturalOrder());

        StringBuilder samePart = new StringBuilder();

        String first = arraylist.getFirst();
        String last = arraylist.getLast();
        int count = 0;
        
        while(count < Math.min(first.length(), last.length())){
            if(first.charAt(count) == last.charAt(count)){
                samePart.append(first.charAt(count));
            } else {
                return samePart.toString();
            }
            count++;
        }

        return samePart.toString();
    }
}