Match Prefix Pairs (Interview Solution)

How to Solve Prefix Pairs

Prefix Pairs Introduction

The Prefix Pairs problem asks us to take a given array and match all words with other words from the list that are a prefix for that word. This problem requires us to construct a Trie from our words, insert them in, and traverse character by character.

Prefix Pairs Problem

Given a list of words, match all words with other words from the list that are a prefix for the word.

Example Input and Output

Example

Input: words = ["abs", "app", "be", "apple", "bee", "better", "bet", "absolute"]
Output: [('app', 'apple'), ('be', 'bee'), ('be', 'better'), ('be', 'bet'), ('abs', 'absolute')]

Prefix Pairs Solutions

To solve this problem, we can use a Trie data structure. A Trie, also known as a prefix tree, is a tree-like data structure that stores a set of strings in a way that allows for efficient prefix-based searching. In our case, we want to find pairs of words where one word is a prefix of the other. By constructing a Trie from the given list of words, we can efficiently search for such pairs.

To begin, we create a Trie by initializing an empty root node. We then iterate through each word in the input list and insert it into the Trie. During the insertion process, we traverse the Trie character by character, creating new nodes if necessary. At the end of each word, we mark the corresponding node as representing a complete word.

Once the Trie is constructed, we can find the prefix pairs by performing a depth-first search on the Trie. Starting from the root node, we recursively explore each branch of the Trie. When we reach a leaf node, we check if the node represents a complete word and if its parent node exists. If both conditions are met, we have found a prefix pair. We collect these pairs and return them as the result.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()  # Initialize the Trie with an empty root node

def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()  # Create a new TrieNode for the character
            node = node.children[char]  # Move to the child TrieNode
        node.is_word = True  # Mark the last TrieNode as representing a complete word

def search_prefix(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return None  # Return None if the prefix is not found in the Trie
            node = node.children[char]
        return node  # Return the TrieNode representing the last character of the prefix

def find_prefix_matches(words):
    trie = Trie()  # Create a new Trie
    matches = []  # List to store the prefix matches

# Insert words into the Trie
    for word in words:
        trie.insert(word)

# Find prefix matches
    for word in words:
        prefix = ""
        node = trie.root
        for char in word:
            prefix += char  # Build the prefix character by character
            node = node.children[char]  # Traverse to the child TrieNode
            if node.is_word and prefix != word:
                # If the current node represents a complete word and the prefix is not equal to the word,
                # we have found a prefix match
                matches.append((prefix, word))
                break

return matches

#driver code
words = ["abs", "app", "be", "apple", "bee", "better", "bet", "absolute"]
matches = find_prefix_matches(words)
print(matches)

Time/Space Complexity Analysis