Longest Common Prefix

1. Problem Description

Write a function to find the longest common prefix among an array of strings.

If there is no common prefix, return the empty string “”.

2. Approach

1. Brute force
2. Trie? tree

3. Implementation

Brute Force

func longestCommonPrefix(strs []string) string {
    count := 0
    longestCommonPrefixDFS(strs, 0, &count)
    if count == 0{return ""}
    return strs[0][:count]
}

func longestCommonPrefixDFS(strs []string, index int, count *int) {
    m := make(map[byte]int, 0)
    for _, str := range strs {
        if index >= len(str) {return}
        m[str[index]]++
    }
    if len(m) == 1{
        (*count)++
        longestCommonPrefixDFS(strs, index+1, count)
    } 
} 

4. References

• 14. Longest Common Prefix - LeetCode