# 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:
= 0
count for char_a, char_b in zip(a, b):
if char_a != char_b:
break
+= 1
count
return count
def longestCommonPrefix(self, arr1: list[int], arr2: list[int]) -> int:
= 0
size_biggest
for a in map(str, sorted(arr1, reverse=True)):
if len(a) <= size_biggest:
break
for b in map(str, arr2):
= self.pfx_elems(a, b)
size if size > size_biggest:
= size
size_biggest
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:
int
terminates: dict[str, Self]
children:
def __init__(
self,
dict[str, Self],
children: int = False,
terminates:
):self.children = children
self.terminates = terminates
```

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