Longest Common Prefix

From LeetCode

problem description / solution

Solution in Python3

class Solution:
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if len(strs) == 0:
            return ''
        for i in range(len(strs[0])):
            for j in range(1, len(strs)):
                if (len(strs[j]) <= i 
                        or strs[0][i] != strs[j][i]):
                    return strs[0][:i]
        return strs[0]

Variants

Word by word

• LeetCode call it horizontal scanning.
• Another sample on GeeksforGeeks

Trie

Get a trie. sample

Binary search for prefix length

This is more time consuming, unless we can compare two string as fast as two characters (in python we can, sometimes). sample

The length of shortest string will be the maximum length of common prefix.