Prefix Pairs Introduction
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
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
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)1class TrieNode:
2 def __init__(self):
3 self.children = {}
4 self.is_word = False
5
6class Trie:
7 def __init__(self):
8 self.root = TrieNode() # Initialize the Trie with an empty root node
9
10 def insert(self, word):
11 node = self.root
12 for char in word:
13 if char not in node.children:
14 node.children[char] = TrieNode() # Create a new TrieNode for the character
15 node = node.children[char] # Move to the child TrieNode
16 node.is_word = True # Mark the last TrieNode as representing a complete word
17
18 def search_prefix(self, prefix):
19 node = self.root
20 for char in prefix:
21 if char not in node.children:
22 return None # Return None if the prefix is not found in the Trie
23 node = node.children[char]
24 return node # Return the TrieNode representing the last character of the prefix
25
26
27def find_prefix_matches(words):
28 trie = Trie() # Create a new Trie
29 matches = [] # List to store the prefix matches
30
31 # Insert words into the Trie
32 for word in words:
33 trie.insert(word)
34
35 # Find prefix matches
36 for word in words:
37 prefix = ""
38 node = trie.root
39 for char in word:
40 prefix += char # Build the prefix character by character
41 node = node.children[char] # Traverse to the child TrieNode
42 if node.is_word and prefix != word:
43 # If the current node represents a complete word and the prefix is not equal to the word,
44 # we have found a prefix match
45 matches.append((prefix, word))
46 break
47
48 return matches
49
50#driver code
51words = ["abs", "app", "be", "apple", "bee", "better", "bet", "absolute"]
52matches = find_prefix_matches(words)
53print(matches)Time/Space Complexity Analysis
- Time Complexity: O(N), where N is the total number of words in the input.
- Space Complexity: O(N), where N is the total number of words.
Watch These Related Mock Interviews
About interviewing.io
interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.
