Find the Length of the Longest Common Prefix

class DigitsTrieNode {
public:
    DigitsTrieNode* childNodes[10];
    DigitsTrieNode() {
        for (int i = 0; i < 10; ++i) {
            childNodes[i] = nullptr;
        }
    }
};

class DigitsTrie {
public:
    DigitsTrieNode* rootNode;

    DigitsTrie() { rootNode = new DigitsTrieNode(); }

    void addNumber(int number) {
        DigitsTrieNode* currentNode = rootNode;
        string numberAsString = to_string(number);
        for (char digit : numberAsString) {
            int index = digit - '0';
            if (!currentNode->childNodes[index]) {
                currentNode->childNodes[index] = new DigitsTrieNode();
            }
            currentNode = currentNode->childNodes[index];
        }
    }

    int longestCommonPrefixLength(int number) {
        DigitsTrieNode* currentNode = rootNode;
        string numberAsString = to_string(number);
        int prefixLength = 0;

        for (char digit : numberAsString) {
            int index = digit - '0';
            if (currentNode->childNodes[index]) {
                prefixLength++;
                currentNode = currentNode->childNodes[index];
            } else {
                break;
            }
        }
        return prefixLength;
    }
};

class PrefixSolution {
public:
    int findLongestCommonPrefix(vector<int>& firstArray, vector<int>& secondArray) {
        DigitsTrie digitsTrie;

        for (int number : firstArray) {
            digitsTrie.addNumber(number);
        }

        int maxPrefixLength = 0;

        for (int number : secondArray) {
            int currentPrefixLength = digitsTrie.longestCommonPrefixLength(number);
            maxPrefixLength = max(maxPrefixLength, currentPrefixLength);
        }

        return maxPrefixLength;
    }
};

The provided C++ code offers a solution to find the length of the longest common prefix between any numbers from two separate arrays. It employs a trie (a tree-like data structure used for storing strings) for efficient prefix matching and searching.

• Data Structure Design: The implementation introduces two classes, DigitsTrieNode and DigitsTrie, where DigitsTrieNode defines the trie node structure capable of holding up to ten child nodes, each corresponding to a digit from 0 to 9. The DigitsTrie class functions to manage the trie including adding numbers and determining the longest common prefix length for a particular number.

• Number Insertion into Trie: When adding a number to the trie, the number is first converted into a string. Each digit of this string is then processed to expand the trie. A new node is created if the corresponding child node for a digit does not exist.

• Longest Common Prefix Calculation: The function longestCommonPrefixLength calculates how many initial digits (prefix) a specified number shares with numbers already in the trie. It iterates through each digit of the number and traverses the corresponding node of the trie until a mismatch is found, returning the length of the matching prefix.

• Finding Maximum Prefix Among Arrays: The PrefixSolution class contains the function findLongestCommonPrefix that, using instances of DigitsTrie, adds all numbers from the first array to the trie. It then checks each number from the second array to determine the maximum length of common prefixes it shares with any of the numbers in the first array.

The method presented is optimal for handling large sets of numbers and efficiently resolving the longest common prefix amongst them, leveraging the trie’s capabilities for fast lookup and insertion. This approach minimizes the need for direct comparisons between each number, significantly reducing computation time relative to a brute-force check of every possible pair of numbers.

class DigitNode {
    DigitNode[] children = new DigitNode[10];  // Holds up to 10 child nodes for each digit
}

class NumberTrie {
    DigitNode root = new DigitNode();  // Root of the trie

    void addNumber(int number) {
        DigitNode current = root;
        String numberStr = Integer.toString(number);
        for (char digit : numberStr.toCharArray()) {
            int index = digit - '0';
            if (current.children[index] == null) {
                current.children[index] = new DigitNode();
            }
            current = current.children[index];
        }
    }

    int searchLongestCommonPrefix(int number) {
        DigitNode current = root;
        String numberStr = Integer.toString(number);
        int length = 0;

        for (char digit : numberStr.toCharArray()) {
            int index = digit - '0';
            if (current.children[index] != null) {
                length++;
                current = current.children[index];
            } else {
                break;
            }
        }
        return length;
    }
}

class NumberMatcher {
    public int computeLongestCommonPrefix(int[] array1, int[] array2) {
        NumberTrie trie = new NumberTrie();

        for (int number : array1) {
            trie.addNumber(number);
        }

        int maximumPrefix = 0;
        for (int number : array2) {
            int length = trie.searchLongestCommonPrefix(number);
            maximumPrefix = Math.max(maximumPrefix, length);
        }

        return maximumPrefix;
    }
}

In the given Java solution, the objective is to determine the longest common prefix length of numeric strings between two arrays. The solution uses a trie data structure to efficiently manage comparisons. The process can be summarized as follows:

• First, a DigitNode class defines a node for the trie each having up to ten children, one for each numeral from 0 to 9.

• The NumberTrie class features methods for adding numbers to the trie and searching for the longest common prefix with a given number.

• Within NumberTrie, the addNumber method converts an integer to its string representation and processes each digit. If a child node for a digit doesn't exist at the current trie node, it gets created.

• The searchLongestCommonPrefix method also converts a given number into its string format and then traverses the trie. For each digit, if a corresponding child node is present, it progresses, and the common length counter is incremented. The traversal stops on finding a non-existent child node for a subsequent digit, returning the count of matched digits up to that point.

• In NumberMatcher class, the computeLongestCommonPrefix method initializes an instance of NumberTrie and loads it with numbers from the first array. Then, it iterates through the second array, computes the prefix length for each number using the trie, and tracks the maximum of these lengths.

• Thus, the computeLongestCommonPrefix returns the length of the longest common prefix found between any number in the first array and any number in the second array, described as an int value.

This solution efficiently uses a trie to manage large number datasets, optimizing the search and insertion operations for determining the longest common prefix among numbers represented as strings.

class Node:
    def __init__(self):
        # Nodes for decimal digits
        self.next = [None] * 10


class DecimalTrie:
    def __init__(self):
        self.root = Node()

    def add_number(self, number):
        current = self.root
        number_string = str(number)
        for digit in number_string:
            index = int(digit)
            if not current.next[index]:
                current.next[index] = Node()
            current = current.next[index]

    def longest_match_length(self, number):
        current = self.root
        number_string = str(number)
        match_length = 0

        for digit in number_string:
            index = int(digit)
            if current.next[index]:
                match_length += 1
                current = current.next[index]
            else:
                break
        return match_length


class MatchFinder:
    def find_max_common_prefix(self, set1, set2):
        trie = DecimalTrie()

        for number in set1:
            trie.add_number(number)

        max_common_prefix = 0

        for number in set2:
            length = trie.longest_match_length(number)
            max_common_prefix = max(max_common_prefix, length)

        return max_common_prefix

The provided Python code defines a solution to find the length of the longest common prefix between two sets of numbers using a Trie (prefix tree) specifically designed for decimal digits. The solution consists of three main classes: Node, DecimalTrie, and MatchFinder.

• Node Class: This class is a basic trie node that has an array of ten elements (representing decimal digits 0-9), each can be a reference to another Node.

• DecimalTrie Class: It is responsible for:

  • Storing the root node.
  • Adding numbers to the trie through the add_number function, which breaks each number into its digits and stores them sequentially in the trie.
  • Finding the longest matching prefix length of a number with those stored in the trie using longest_match_length. This method checks each digit of the given number within the trie, maintaining a count of consecutively matching digits.

• MatchFinder Class:

  • It contains a method find_max_common_prefix which builds a trie for the first set of numbers and then checks for the longest common prefix for numbers in the second set against this trie.
  • It updates the maximum found prefix length for each number comparison between the sets.

This structured approach ensures efficient matching, leveraging the characteristics of trie data structures for quick prefix lookup and insertion. The final result is the length of the maximum prefix that is common between any number in the first set and any number in the second set.