Longest Common Prefix

Find the longest prefix shared by every string.

longestCommonPrefix([]string{"flower", "flow", "flight"})   // "fl"
longestCommonPrefix([]string{"dog", "racecar", "car"})      // ""

Compare vertically

The instinct is to compare the first two words, then fold that result against the third, and so on. That works and reads every word to its end.

Turning the comparison ninety degrees is better: take the first word as a template and check one column at a time across all the words. The first column that disagrees ends the prefix.

func longestCommonPrefix(strs []string) string {
    for i, v := range []byte(strs[0]) {
        for _, str := range strs {
            if i == len(str) || v != str[i] {
                return str[0:i]
            }
        }
    }

    return strs[0]
}

One thing worth tidying

The return is str[0:i] — a slice of the inner loop’s variable. It happens to be correct: everything up to i matched, so str and strs[0] agree there. But the value being returned comes from whichever word triggered the exit, which is not what the reader expects.

return strs[0][:i]

Same string, and now it obviously comes from the template. When two expressions are provably equal, prefer the one whose provenance is clear.

The alternatives

Sort and compare the ends. Sorting the slice lexicographically puts the two most dissimilar strings first and last, so their common prefix is the answer for all of them. $O(n \log n \cdot L)$ — slower, and a genuinely nice observation.

Divide and conquer. Split, solve halves, intersect. Same complexity as the column walk, more code, and it parallelises.

A trie. Insert every word and walk down while each node has exactly one child and is not a word end. Overkill for one query, and exactly right if you are answering many prefix questions over the same set — which is what a trie is for.