Longest Common Prefix


#1

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

Example 2:

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

Note:

All given inputs are in lowercase letters a-z.


#2

Looking at all strings take a lot of time, instead if we sort them in ascending order and then compare the shortest with the largest, we could easily find out the longest common prefix. This works because the prefix has to be common across all of them.

Below is a 0 ms solution in golang.

func longestCommonPrefix(strs []string) string {
    
    if len(strs) ==0{
        return ""
    }
    sort.Strings(strs)
    
    shrtStr := []rune(strs[0])
    longStr := []rune(strs[len(strs)-1])
    
    result := make([]rune,0)
    longLen := len(longStr)
    for i:=0;i<len(shrtStr);i++{
        if longLen> i && shrtStr[i] == longStr[i]{
            result = append(result, longStr[i])
        } else{
            return string(result)
        }
    }
    
    return string(result)
}

#3

Similar approach but even less code.

func longestCommonPrefix(strs []string) string {
    if len(strs) == 0{
        return ""
    }
    
    sort.Strings(strs)
    
    for i:=0;i<len(strs[0]);i++ {
        if strs[0][i] != strs[len(strs)-1][i]{
            return strs[0][0:i]
        }
    }
    
    return strs[0]
}