【LittleDuck_LeetCodeNote】14 - Longest Common Prefix

【Instagram】 / 【巴哈姆特小屋】 / 【Vocus方格子】 / 【Medium】
喜歡的話就按個愛心或贊助ㄅ。

Question and Hints:

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 %)