<p>You are given two arrays with <strong>positive</strong> integers <code>arr1</code> and <code>arr2</code>.</p>

<p>A <strong>prefix</strong> of a positive integer is an integer formed by one or more of its digits, starting from its <strong>leftmost</strong> digit. For example, <code>123</code> is a prefix of the integer <code>12345</code>, while <code>234</code> is <strong>not</strong>.</p>

<p>A <strong>common prefix</strong> of two integers <code>a</code> and <code>b</code> is an integer <code>c</code>, such that <code>c</code> is a prefix of both <code>a</code> and <code>b</code>. For example, <code>5655359</code> and <code>56554</code> have a common prefix <code>565</code> while <code>1223</code> and <code>43456</code> <strong>do not</strong> have a common prefix.</p>

<p>You need to find the length of the <strong>longest common prefix</strong> between all pairs of integers <code>(x, y)</code> such that <code>x</code> belongs to <code>arr1</code> and <code>y</code> belongs to <code>arr2</code>.</p>

<p>Return <em>the length of the <strong>longest</strong> common prefix among all pairs</em>.<em> If no common prefix exists among them</em>, <em>return</em> <code>0</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> arr1 = [1,10,100], arr2 = [1000]
<strong>Output:</strong> 3
<strong>Explanation:</strong> There are 3 pairs (arr1[i], arr2[j]):
- The longest common prefix of (1, 1000) is 1.
- The longest common prefix of (10, 1000) is 10.
- The longest common prefix of (100, 1000) is 100.
The longest common prefix is 100 with a length of 3.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> arr1 = [1,2,3], arr2 = [4,4,4]
<strong>Output:</strong> 0
<strong>Explanation:</strong> There exists no common prefix for any pair (arr1[i], arr2[j]), hence we return 0.
Note that common prefixes between elements of the same array do not count.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= arr1.length, arr2.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= arr1[i], arr2[i] &lt;= 10<sup>8</sup></code></li>
</ul>

class Trie:

    def __init__(self):
        self.end = False
        self.elements = [None for i in range(10)]

    def insert(self, word):
        if word == "":
            self.end = True
            return

        firstChar = word[0]
        nextTrie = self.elements[int(firstChar)]
        if not nextTrie:
            nextTrie = Trie()
        self.elements[int(firstChar)] = nextTrie
        nextTrie.insert(word[1:])

    def getLengthOfPrefix (self, word, currLen):
        if word == "":
            return currLen
        firstChar = word[0]
        nextTrie = self.elements[int(firstChar)]
        if not nextTrie:
            return currLen
        return nextTrie.getLengthOfPrefix(word[1:], currLen + 1)


class Solution:
    def longestCommonPrefix(self, arr1: List[int], arr2: List[int]) -> int:
        """
        arr1 and arr2 both contains "words"

        we want to find the longest common prefix between any 2 pairs of words, where one word belongs to arr 1
        and 1 word belongs to arr2

        My initial thoughts, we should jsut use a trie
        so for arr 1, we store all the words into the trie, then for each word in arr 2, we traverse the trie to find the maximum common prefix
        this will be O(total length of words) O(n) space also

        if we have words
        1223
        1223
        length of prefix is 4? 
        """
        trie = Trie()
        for num in arr1:
            trie.insert(str(num))
        
        maxLen = 0
        for num in arr2:
            maxLen = max(maxLen, trie.getLengthOfPrefix(str(num), 0))
        return maxLen        
38168