LeetCode #14 Longest Common Prefix Solution & Explanation

LeetCode Problem

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

Solution

The first solution is easy.

1. Set the first element of array as temp char.
2. Iterate the left elements, and check each character one by one.

C# Solution

Solution1

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 = 0; j < strs.Length; j++) 
            {
                if (strs[j].Length == i || strs[j][i] != tmpChar) 
                {
                    return strs[0].Substring(0, i);
                }
            }
        }
        return strs[0]; 
    }
}

Runtime : 113ms、106ms、167ms

Another way is – 【StartsWith】, it can check if the string start with the prefix string.

If not, than we remove the last character of string to check again.

Solution2

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;
    }
}

Runtime : 140ms、112ms、125ms

Java Solution

Solution1

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 = 0; j < strs.length; j++) 
            {
                if (strs[j].length() == i || strs[j].charAt(i) != tmpChar) 
                {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0]; 
    }
}

Runtime : 1ms

⭐Solution2

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;
    }
}

⭐Runtime : 0~1ms⭐

Python3 Solution

Solution1

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(0,len(strs)):
                if (len(strs[j]) == i or strs[j][i] != tmp):
                    return strs[0][:i];

        return strs[0]; 

Runtime : 63ms、46ms、74ms

⭐Solution2

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;

Runtime : 41ms、56ms、49ms

JavaScript Solution

Solution1

/**
 * @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 = 0; j < strs.length; j++) 
        {
            if (strs[j].length == i || strs[j][i] != tmpChar) 
            {
                return strs[0].substring(0, i);
            }
        }
    }
    return strs[0]; 
};

Solution2

/**
 * @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;
};

Conclusion

🧡If my solution helps, that is my honor!

🧡You can support me by clicking some ad, Thanks a lot !

Cover Photo – Photo by Sincerely Media on Unsplash

The problem link : Longest Common Prefix – LeetCode

Technology Article

• Understanding Hive ransomware – Preventing becoming the next victim2023-07-24
• How to Effectively Manage Personnel Permissions using Binary-Base Logic Control2023-04-04
• Zambian Central Bank refused to pay ransom to hackers but sent pornographic picture !2022-06-06

Latest Post

• LeetCode #168 Excel Sheet Column Title Solution & Explanation2024-04-22
• LeetCode #2073 Time Needed to Buy Tickets Solution & Explanation2024-04-14
• LeetCode #1700 Number of Students Unable to Eat Lunch Solution & Explanation2024-04-09
• LeetCode #1544 Make The String Great Solution & Explanation2024-04-07
• LeetCode #977 Squares of a Sorted Array Solution & Explanation2024-03-20