【LittleDuck_LeetCodeNote】14 - Longest Common Prefix

Question and Hints:

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: strs = ["flower","flow","flight"]

Output: "fl"

Example 2:

Input: strs = ["dog","racecar","car"]

Output: ""

Explanation: There is no common prefix among the input strings.

Constraints:

• 1 = strs.length = 200
• 0 = strs[i].length = 200
• strs[i] consists of only lowercase English letters.

---

First Solution

💡 這邊的思路是先從前兩個字串找出共同前序， 再用共同前序去和其它字串比較， 比較結果先存在temp，如果temp比較短，就取代掉result， 迴圈結束後回傳最後的共同前序result。 另外有幾個前提先設定好：

• 如果長度為1，直接回傳第一個值。
• 如果長度為2，第一次比較完就直接回傳result。
• 如果有空字串，直接break，或是回傳result，反正就是不要理他。

不過奇怪的是，不知道為什麼程式完全不理 strs[k].length() == 0 (25行)的條件，因此程式不斷出錯，所以沒有submit的結果。

class Solution {

    public String longestCommonPrefix(String[] strs) {

        String temp = "", result = "";

        // if strs only ony string, return itself.

        if(strs.length == 1)

            return strs[0];



        // Find strs[0] & strs[1] the longest same part.

        int shortLen = strs[0].length() >= strs[1].length() ?  strs[1].length() : strs[0].length();

        

        for(int i=0; i<shortLen; i++){

            if(strs[0].charAt(i) == strs[1].charAt(i))

                result += strs[0].charAt(i);

            else

                break;

        }



        // if strs only ony string, you can return result at the time.

        if(strs.length == 2)

            return result;



        // For arrays of length greater than 2, use temp to detect other words.

        for(int k=2; k<strs.length; k++){

            temp = "";

            if(strs[k].length() == 0)

                return result;

            int min = result.length() < strs[k].length() ? result.length() : strs[k].length();

            for(int m=0; m<min; m++){

                if(result.charAt(m) == strs[k].charAt(m))

                    temp += result.charAt(m);

            }

            if(temp.length() <= result.length())

                result = temp;

        }



        // get the longest common prefix, return.

        return result;

    }

}

⏰ Runtime: ?? ms (?? %)

📦 Memory: ?? MB (?? %)

---

Upgrade Solution

the fastest solution:

💡 前面用縮短的共同前序去做比較的思考方向沒錯，但有更精簡的過程。

• 如果strs是空的，那就不用比了。
• 先預設共同前序prefix是第一個字串的所有內容。
• 用prefix去跟每一個字串比較，比較過程中如果prefix不吻合，就砍掉最後一個字再重新比較一次，直到完全吻合為止，就像削馬鈴薯皮一樣。過程中如果prefix沒了，也就是馬鈴薯被削成粉了，就直接回傳空字串。
• 直到每一個字串都比較完後，回傳剩下的共同前序。

startsWith(prefix) 是Java裡面用於比對字串的函式， 用來確認字串是否有以prefix作為前序，有就回傳true，沒有就回傳false。

class Solution {

    public String longestCommonPrefix(String[] strs) {

        if (strs == null || strs.length == 0) {

            return "";

        }



        String prefix = strs[0];



        for (int i = 1; i < strs.length; i++) {

            while (!strs[i].startsWith(prefix)) {

                prefix = prefix.substring(0, prefix.length() - 1);

                if (prefix.isEmpty()) {

                    return "";

                }

            }

        }



        return prefix;

    }

}

⏰ Runtime: 0 ms (100 %)

📦 Memory: 40.8 MB (51.26 %)

---

Upgrade Solution 2

the shortest solution:

💡 這個是完全不同的思路：以剛才馬鈴薯的比喻來說，這個就是挑出差異最大的兩顆馬鈴薯，然後直接把不同的部分切掉，只留下相同的部分。

• 先對字串進行 Arrays.sort ，確保內容的長度從頭到尾是由小到大，並且依字母順序排列好。例如：[”aaa”, “aa”, “aaa”]排序後會變成["aa", "aaa", “aaa"] ；{ "atocmic", "atoamcy", "atocshie", "atbeijgnlkd" }變成{ “atbeijgnlkd”, “atoamcy”, “atocmic”, “atocshie” }
• idx代表的是，到第幾個字母前的字串，都屬於共同前序。所以idx不能比s1或s2長，若idx所屬位置字元相同，idx++，檢查下一個字母，若不相同，表示共同前序到此為止，離開迴圈。
• 最後回傳s1到第idx個字元之前的所有內容，即為共同前序。

class Solution {

    public String longestCommonPrefix(String[] strs) {

        Arrays.sort(strs);

        String s1 = strs[0];

        String s2 = strs[strs.length-1];

        int idx = 0;

        while(idx < s1.length() && idx < s2.length()){

            if(s1.charAt(idx) == s2.charAt(idx)){

                idx++;

            } else {

                break;

            }

        }

        return s1.substring(0, idx);

    }

}

⏰ Runtime: 1 ms (76.66 %)

📦 Memory: 40.9 MB (43.56 %)