1065. Index Pairs of a String
Model: qwen2.5-coder:14b
Topics: String,Trie
FAANG asked: 1
Acceptance rate: 61.0%
Problem Breakdown
The problem requires finding all index pairs [i, j] in a given text string such that the substring text[i]...text[j] matches any of the strings in the list words. The inputs are:
- A single string
text. - A list of strings
words.
The output is a list of index pairs. Each pair [i, j] indicates that the substring from index i to j (inclusive) in text matches one of the words in words. The pairs should be returned in sorted order first by their starting index i, and then by their ending index j.
Implicit constraints:
- All strings contain only lowercase English letters.
- Words in
wordsare unique.
Edge cases to consider:
textorwordscould be empty.- Substrings can overlap, as shown in Example 2.
Intuition
A brute-force approach would involve checking every possible substring of text against each word in words. This would have a time complexity of O(n^3 * m), where n is the length of text and m is the average length of words in words, which is inefficient given the constraints.
A better approach involves using a Trie (prefix tree) to store all the words from words. This allows for efficient substring matching. By traversing the text and checking each possible starting index against the Trie, we can find matches more efficiently.
Approach
- Build a Trie: Insert all words from
wordsinto a Trie. - Search in Trie: For each character in
text, perform a depth-first search (DFS) to check if any substring starting at that character exists in the Trie. - Collect Results: If a word is found in the Trie, record the start and end indices of the substring.
Complexity Analysis
- Time Complexity: O(n * m), where n is the length of
textand m is the average length of words inwords. Building the Trie takes O(m) time for each word, and searching throughtextwith DFS takes O(n * m) time. - Space Complexity: O(m), where m is the total number of characters in all words combined. This is the space required to store the Trie.
Solution
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True
def indexPairs(text: str, words: List[str]) -> List[List[int]]:
trie = Trie()
for word in words:
trie.insert(word)
result = []
def dfs(start_index, node):
if node.is_end_of_word:
result.append([start_index, start_index + len(path) - 1])
if start_index >= len(text):
return
next_char = text[start_index]
if next_char in node.children:
dfs(start_index + 1, node.children[next_char], path + next_char)
for i in range(len(text)):
dfs(i, trie.root, "")
result.sort()
return result
Edge Cases Handled
- Empty
text: The loop overtextwill not execute, and an empty list is returned. - Empty
words: The Trie remains empty, and no matches are found. - Overlapping Substrings: The DFS allows for overlapping substrings to be matched, as shown in Example 2.