LeetCode #14 Longest Common Prefix 最長的共通字串

內容目錄

文章觀看次數: 648

LeetCode題目翻譯

英文原文如下

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 “”.

中文翻譯

撰寫一個 Function 從一個字串陣列中尋找最長的共通前綴

若無共通的前綴，則回傳空白字串 “”

從範例1可以看到，本來【flower】跟【flow】共通的前綴是【flow】

但加上第三個字串【flight】，只剩下前2個單字符合了，故回傳【fl】

解題思路

第一個解決方法採用以下的邏輯

將陣列的第一個字串設為對照組

接著從第一個字串的第一個字元開始

跟其他字串一個一個比較 ( * j = 1 )

要是其他字串對應位置的字元跟對照組的不相同，就回傳相應長度的字串

例如【flower】跟【flight】，對照組的第三個字元是 o ，但另一邊則是 i

另一個回傳的條件則是其他字串的長度不夠的時候 ( strs[j].Length == i )

C# 解決方案

方案1

public class Solution {
    public string LongestCommonPrefix(string[] strs)
    {
        for (int i = 0; i < strs[0].Length; i++) 
        {
            char tmpChar = strs[0][i]; 
            for (int j = 1; j < strs.Length; j++) 
            {
                if (strs[j].Length == i || strs[j][i] != tmpChar) 
                {
                    return strs[0].Substring(0, i);
                }
            }
        }
        return strs[0]; 
    }
}

時間複雜度 : O(n²)

方案2

public class Solution {
    public string LongestCommonPrefix(string[] strs) {
        
        string res = strs[0];

        for(int i = 1;i<strs.Length;i++)
        {        
            while(true)
            {
                if(strs[i].StartsWith(res))
                {
                    break;
                }
                else
                {
                    if(res.Length == 1)
                    {
                        return "";
                    }
                    res = res.Substring(0, res.Length-1);
                }
            }
        }
        
        return res;
    }
}

第二種作法則是使用 StartsWith 這個內建的函式

先建立一個 res 的字串 ( 預設與第一個字串相同 )

之後依序跑其他字串

若其他字串的開始不是 res ，則將 res 最後一位移除再跑一次

時間複雜度 : O(n²)

Java解決方案

方案1

class Solution {
    public String longestCommonPrefix(String[] strs) {
        for (int i = 0; i < strs[0].length(); i++) 
        {
            char tmpChar = strs[0].charAt(i); 
            for (int j = 1; j < strs.length; j++) 
            {
                if (strs[j].length() == i || strs[j].charAt(i) != tmpChar) 
                {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0]; 
    }
}

⭐方案2

class Solution {
    public String longestCommonPrefix(String[] strs) {
        String res = strs[0];

        for(int i = 1;i<strs.length;i++)
        {
            while(true)
            {
                if(strs[i].startsWith(res))
                {
                    break;
                }
                else
                {
                    if(res.length() == 1)
                    {
                        return "";
                    }
                    res = res.substring(0, res.length()-1);
                }
            }
        } 
        
        return res;
    }
}

Python3 解決方案

方案1

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        for i in range(0,len(strs[0])):
        
            tmp = strs[0][i]; 
            
            for j in range(1,len(strs)):
                if (len(strs[j]) == i or strs[j][i] != tmp):
                    return strs[0][:i];

        return strs[0];

方案2

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        res = strs[0];

        for i in range(1,len(strs)):
            while(True):
                if(strs[i].startswith(res)):
                    break;
                    
                else:
                    if(len(res) == 1):
                        return "";
                    res = res[:len(res)-1];
        
        return res;

JavaScript 解決方案

方案1

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    for (var i = 0; i < strs[0].length; i++) 
    {
        var tmpChar = strs[0][i]; 
        for (var j = 1; j < strs.length; j++) 
        {
            if (strs[j].length == i || strs[j][i] != tmpChar) 
            {
                return strs[0].substring(0, i);
            }
        }
    }
    return strs[0]; 
};

方案2

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {

    var res = strs[0];

    for(var i = 1;i<strs.length;i++)
    {
        while(true)
        {
            if(strs[i].startsWith(res))
            {
                break;
            }
            else
            {
                if(res.length == 1)
                {
                    return "";
                }
                res = res.substring(0, res.length-1);
            }
        }
    } 

    return res;
};

結論

以難度來說，這題算是不難的 ( 大家看上面的解答就能知道不麻煩 )

但是 Acceptance Rate 卻只有 40% 多一點，說明還是需要思考一下的，要是亂提交很容易錯誤

🧡如果這篇文章有幫上你的一點點忙，那是我的榮幸

🧡可以的話，幫我的FaceBook 粉絲專頁按個讚，我會很感謝的

✅如有任何疑問，歡迎透過留言或messenger讓我知道 !

題目連結 : Longest Common Prefix – LeetCode

LeetCode題目翻譯

解題思路

C# 解決方案

Java解決方案

Python3 解決方案

JavaScript 解決方案

結論

相關文章

LeetCode #231 Power of Two 二的次方

LeetCode #326 Power of Three 三的次方

發佈留言取消回覆