Longest Common Prefix, sets of Integers [Trie]

XXX.Longest Common Prefix Using Trie

Trie

String

Problem Statement:

Given two arrays of integers arr1 and arr2, find the longest common prefix of digits between any number from arr1 and any number from arr2. For example, the numbers 12345 and 12367 have a common prefix of 123 with length 3.

Algorithm:

1. Create a Trie structure to store numbers as sequences of digits (0-9).
2. Insert all numbers from arr1 into the Trie, where each digit is a child node.
3. For each number in arr2, traverse the Trie to determine the length of its longest common prefix with any number in arr1.
4. Keep track of the maximum prefix length found during traversal.
5. Return the maximum length of the common prefix as the result.

Complexity:

Time: O(n × m + k × l), where n is the size of arr1, k is the size of arr2, m and l are the average number of digits in numbers of arr1 and arr2 respectively. | Space: O(n × m) for storing numbers in the Trie.

Java Implementation:

class TrieNode {
    TrieNode[] children = new TrieNode[10]; // Each node has up to 10 children (digits 0-9)
}

class Trie {

    TrieNode root = new TrieNode();

    // Insert a number into the Trie as a string of digits
    void insert(int num) {
        TrieNode node = root;
        for (char digit : Integer.toString(num).toCharArray()) {
            int idx = digit - '0';
            if (node.children[idx] == null)
                node.children[idx] = new TrieNode();
            node = node.children[idx];
        }
    }

    // Find the longest common prefix of a number in arr2 with the Trie
    int findLongestPrefix(int num) {
        TrieNode node = root;
        int len = 0;
        for (char digit : Integer.toString(num).toCharArray()) {
            int idx = digit - '0';
            if (node.children[idx] != null) {
                len++; // Continue if the digit matches
                node = node.children[idx];
            } else break; // Stop when no match is found
        }
        return len;
    }
}

public class Solution {

    public int longestCommonPrefix(int[] arr1, int[] arr2) {
        Trie trie = new Trie();
        int longestPrefix = 0;

        // Insert all numbers from arr1 into the Trie
        for (int num : arr1) trie.insert(num);

        // Find the longest prefix match for each number in arr2
        for (int num : arr2)
            longestPrefix = Math.max(longestPrefix, trie.findLongestPrefix(num));

        return longestPrefix;
    }
}
                

Python Implementation:

class TrieNode:
    def __init__(self):
        self.children = [None] * 10

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, num):
        node = self.root
        for digit in str(num):
            idx = int(digit)
            if not node.children[idx]:
                node.children[idx] = TrieNode()
            node = node.children[idx]

    def find_longest_prefix(self, num):
        node = self.root
        length = 0
        for digit in str(num):
            idx = int(digit)
            if node.children[idx]:
                length += 1
                node = node.children[idx]
            else:
                break
        return length

class Solution:
    def longestCommonPrefix(self, arr1, arr2):
        trie = Trie()
        longest_prefix = 0

        # Insert all numbers from arr1 into the Trie
        for num in arr1:
            trie.insert(num)

        # Find the longest prefix match for each number in arr2
        for num in arr2:
            longest_prefix = max(longest_prefix, trie.find_longest_prefix(num))

        return longest_prefix
                

C++ Implementation:

struct TrieNode {
    TrieNode* children[10] = {nullptr};
};

class Trie {
public:
    TrieNode* root = new TrieNode();

    void insert(int num) {
        TrieNode* node = root;
        for (char digit : to_string(num)) {
            int idx = digit - '0';
            if (!node->children[idx])
                node->children[idx] = new TrieNode();
            node = node->children[idx];
        }
    }

    int findLongestPrefix(int num) {
        TrieNode* node = root;
        int length = 0;
        for (char digit : to_string(num)) {
            int idx = digit - '0';
            if (node->children[idx]) {
                length++;
                node = node->children[idx];
            } else break;
        }
        return length;
    }
};

class Solution {
public:
    int longestCommonPrefix(vector& arr1, vector& arr2) {
        Trie trie;
        int longestPrefix = 0;

        // Insert all numbers from arr1 into the Trie
        for (int num : arr1) trie.insert(num);

        // Find the longest prefix match for each number in arr2
        for (int num : arr2)
            longestPrefix = max(longestPrefix, trie.findLongestPrefix(num));

        return longestPrefix;
    }
};