LeetCode 14（上）：硬幹解法的三個坑

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 "".

如果字串陣列中沒有共同前綴，則回傳空字串””。

*前綴：加在某詞前面的詞。

A + B = AB ⇒ A為前綴 例： Dum + p =>我們可以說 Dump 這個字有 Dum這個前綴

範例 1：

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

範例 2:

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

參數限制：

• 字串陣列的長度區間為 1 ~ 200 之間
• 字串陣列中的每個字串，長度區間為 0 ~ 200
• 字串陣列中的每個字串，只會有小寫英文字母(如果字串陣列不是空的)

---

解法不只一種，下面貼上初次解題硬幹方式的解法及思路，然後提一下這樣解的問題在哪

初次硬幹

public String longestCommonPrefix(String[] strs) {
    String minimumString = "";
    int minimum = 300;
    for(int i = 0;i<strs.length;i++){
        if(strs[i].length() < minimum){
            minimum = strs[i].length();
            minimumString = strs[i];
        }
    }
    if(minimumString.equals("")){
        return "";
    }
    for(int i = 0;i<strs.length;i++){
        String target = strs[i];
        int lastIndex = minimumString.length() - 1;
        while(!target.startsWith(minimumString)){
            if(minimumString.equals("")){
                return "";
            }
            minimumString = minimumString.substring(0,lastIndex);
            lastIndex--;
        }
    }

    return minimumString;

}

解題思路：

核心邏輯是，最長共同前綴不可能大於長度最小的字。

假設陣列長這樣 ["flower","flow","flowchart"]

最長共同前綴不可能大於 “flow” ，所以這樣解：

1. 先找出陣列中長度最小的字
2. 遞迴陣列，檢查陣列中的字串是否符合最小的字，不符合就砍尾巴
3. 當陣列跑完，或者最小字串被砍完，答案就出來了

這個版本可以AC ，但有幾個比較關鍵的問題

就是韓國炸雞、薯條、薯片三兄弟

好抱歉，講認真的

三個主要問題是：

1. for 裡面 有while => 雙層迴圈
2. 比較字串時，使用的是 startsWith
3. 頻繁使用 substring 建立新字串

這三個問題會導致什麼後果？ 我又該如何修改？

下一篇跟你說