Daily Question 9/24/2024: Longest Common Prefix.

Use a trie to find the longest common prefix shared by elements in the product of two arrays.

The problem statement may be found here.

Solutions

Trivial Solution

The trivial solution was terribly slow and timed out. Here it is.

class SolutionTrivial:

    def pfx_elems(self, a: str, b: str) -> int:

        count = 0
        for char_a, char_b in zip(a, b):
            if char_a != char_b:
                break

            count += 1

        return count

    def longestCommonPrefix(self, arr1: list[int], arr2: list[int]) -> int:

        size_biggest = 0

        for a in map(str, sorted(arr1, reverse=True)):
            if len(a) <= size_biggest:
                break

            for b in map(str, arr2):
                size = self.pfx_elems(a, b)
                if size > size_biggest:
                    size_biggest = size

        return size_biggest

Trie Solution

Using a trie is very effective since it takes linear time to build the trie and linear time to search it. First, below is the trie implementation:

# start snippet trie_min
class TrieNode:
    terminates: int
    children: dict[str, Self]

    def __init__(
        self,
        children: dict[str, Self],
        terminates: int = False,
    ):
        self.children = children
        self.terminates = terminates

This places in the \(59\%\) for runtime \(30\%\) quantile for memory.