Coding Puzzle: Longest Common Prefix

• Leetcode 14
• Difficulty: Easy

Problem Definition

Find the longest common prefix string amongst an array of strings.

Examples

Some test cases to verify our solution.

assert lcp(["flower", "flow", "flight"]) == "fl"
assert lcp(["dog", "racecar", "race"]) == ""

Solution

def lcp(strings: list[str]) -> str:
    if not strings:
        return ""
    i = 0
    l = len(strings)
    while 1:
        c = None
        for j in range(l):
            if i >= len(strings[j]):
                return strings[0][:i]
            if c is None:
                c = strings[j][i]
            elif c != strings[j][i]:
                return strings[0][:i]
        i += 1

Complexity

Let $n =$ len(strings) (number of strings).

Runtime complexity should be $O(n)$.

Auxiliary space complexity should be $O(1)$.