Index Pairs of a String

▶

Steps

setup

Initialize Trie Root

Create the root node of the trie with no children and not marked as end of word.

💡 The root node is the starting point for inserting all words and for searching substrings.

Line:

root = TrieNode()

💡 The trie starts empty and will grow as words are inserted.

insert

Insert word 'story' into trie - insert 's'

Start inserting the first word 'story'. Add child node for 's' under root since it does not exist.

💡 Inserting characters one by one builds the trie structure representing all words.

Line:

if c not in node.children:
    node.children[c] = TrieNode()

💡 New nodes are created only when the character path does not exist yet.

insert

Insert word 'story' into trie - insert 't'

Continue inserting 'story'. Add child node for 't' under 's' node.

💡 Each character extends the path deeper into the trie.

Line:

if c not in node.children:
    node.children[c] = TrieNode()

💡 Trie nodes branch only when needed for new characters.

insert

Insert word 'story' into trie - insert 'o', 'r', 'y'

Insert remaining characters 'o', 'r', 'y' for 'story', creating new nodes sequentially.

💡 Completing the insertion of a word marks the end node as a word end.

Line:

node = node.children[c]
node.word_end = True

💡 Marking end_of_word allows recognizing complete words during search.

insert

Insert word 'fleet' into trie - insert 'f', 'l', 'e', 'e', 't'

Insert the word 'fleet' character by character, creating new nodes under root.

💡 Words with different prefixes create new branches in the trie.

Line:

for c in w:
    if c not in node.children:
        node.children[c] = TrieNode()

💡 Trie branches represent different word prefixes.

insert

Insert word 'leetcode' into trie - insert 'l', 'e', 'e', 't', 'c', 'o', 'd', 'e'

Insert 'leetcode' character by character, creating new nodes under root's children.

💡 Words sharing prefixes reuse existing nodes; new nodes are added only when needed.

Line:

for c in w:
    if c not in node.children:
        node.children[c] = TrieNode()

💡 Trie efficiently shares prefixes among words.

traverse

Start DFS from index 0 in text

Begin DFS from root node at text index 0 ('t'), searching for matching substrings.

💡 DFS explores trie paths matching text substrings starting at each index.

Line:

for i in range(n):
    dfs(root, i, i)

💡 Starting DFS at each index ensures all substrings are checked.

traverse

DFS from index 3: match 's' in trie

At text index 3, character 's' matches a child of root. Move to node 's'.

💡 Matching characters in text to trie nodes guides DFS traversal.

Line:

if c in node.children:
    dfs(node.children[c], i+1, start)

💡 DFS prunes search paths when characters don't match.

traverse

DFS continues matching 't', 'o', 'r', 'y' from index 3

DFS matches characters 't', 'o', 'r', 'y' sequentially in trie nodes, moving active path deeper.

💡 Following the trie path matches the substring 'story' in text.

Line:

if node.word_end:
    res.append([start, i-1])

💡 Detecting end_of_word nodes during DFS identifies matched words.

traverse

DFS from index 9: match 'f' and find 'fleet'

Starting at index 9 ('f'), DFS matches 'f', 'l', 'e', 'e', 't' in trie, recording [9,13].

💡 DFS finds another word starting at a different index in text.

Line:

if node.word_end:
    res.append([start, i-1])

💡 DFS efficiently finds multiple matches by traversing trie paths.

traverse

DFS from index 10: match 'l' and find 'leetcode'

Starting at index 10 ('l'), DFS matches 'l', 'e', 'e', 't', 'c', 'o', 'd', 'e' in trie, recording [10,17].

💡 DFS finds the longest word starting at index 10 in text.

Line:

if node.word_end:
    res.append([start, i-1])

💡 DFS can find overlapping matches starting at different indices.

prune

Complete DFS for all indices and sort results

After DFS from all indices, collected results are sorted to produce final output.

💡 Sorting ensures index pairs are in ascending order as required.

Line:

res.sort()
return res

💡 Final sorting organizes matches for output clarity.

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

class Solution:
    def indexPairs(self, text, words):
        root = TrieNode()  # STEP 1
        for w in words:  # STEP 2-6
            node = root
            for c in w:
                if c not in node.children:
                    node.children[c] = TrieNode()  # STEP 2-6
                node = node.children[c]
            node.word_end = True  # STEP 4,6

        res = []
        n = len(text)

        def dfs(node, i, start):
            if node.word_end:
                res.append([start, i-1])  # STEP 9,10,11
            if i == n:
                return
            c = text[i]
            if c in node.children:
                dfs(node.children[c], i+1, start)  # STEP 8-11

        for i in range(n):
            dfs(root, i, i)  # STEP 7

        res.sort()  # STEP 12
        return res

if __name__ == '__main__':
    sol = Solution()
    text = "thestoryofleetcodeandme"
    words = ["story","fleet","leetcode"]
    print(sol.indexPairs(text, words))

📊

Index Pairs of a String - Watch the Algorithm Execute, Step by Step

Watching the trie construction and DFS search step-by-step reveals how the algorithm efficiently finds all substring matches without redundant checks.

insert

insert

story

s

insert

story

st

insert

story

story*

insert

fleet

story*fleet*

insert

leetcode

story*fleet*leetcode*

search

story*fleet*leetcode*

search

s

story*fleet*leetcode*

search

story

story*fleet*leetcode*

search

fleet

story*fleet*leetcode*

search

leetcode

story*fleet*leetcode*

search

story*fleet*leetcode*

Search: [[3,7],[9,13],[10,17]]

Key Takeaways

✓ Building a trie from the words allows efficient prefix matching during substring search.

This is hard to see from code alone because the trie structure and its reuse of prefixes is abstract.

✓ DFS from each index in the text explores all possible substrings starting there, pruning paths early when no match exists.

Visualizing DFS traversal clarifies how the algorithm avoids unnecessary checks.

✓ Recording matches when reaching end_of_word nodes captures all valid substrings, including overlapping ones.

Seeing matches recorded during traversal helps understand how multiple results are found.

Practice

1. You are given an array of integers and a range [low, high]. You need to count the number of pairs (i, j) with i < j such that the XOR of nums[i] and nums[j] lies within the given range. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Use a brute force nested loop to check all pairs and count those with XOR in the range.

B. Use dynamic programming to store counts of XOR values for prefixes and combine them.

C. Sort the array and use two pointers to find pairs with XOR in the range.

D. Build a bitwise trie of the numbers and for each number, query how many previously inserted numbers produce XOR less than or equal to a limit, then combine results for the range.

Solution

1. Step 1: Understand the problem constraints

   The problem requires counting pairs with XOR in a range efficiently, which brute force (nested loops) is too slow for large inputs.

2. Step 2: Identify the suitable data structure

   A bitwise trie allows efficient counting of numbers with XOR less than a limit by traversing bits from most significant to least significant.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Bitwise trie approach is known to solve XOR range queries optimally [OK]

Hint: Bitwise trie enables efficient XOR range counting [OK]

Common Mistakes:

• Thinking sorting + two pointers works for XOR ranges
• Assuming DP can handle XOR pairs directly
• Believing brute force is optimal

2. Consider the following Python code snippet implementing the optimal approach to count pairs with XOR less than a limit using a bitwise trie. Given the input nums = [1, 4, 2], and limit = 3, what is the final return value of countPairsLessThan(nums, limit)?

easy

A. 2

B. 4

C. 3

D. 5

Solution

1. Step 1: Trace insertions and queries for nums=[1,4,2], limit=3

   Initially, trie is empty. For num=1, query returns 0 (no previous numbers), then insert 1. For num=4, query counts pairs with XOR<3 with 1, which is 1 (1^4=5>3, so 0), then insert 4. For num=2, query counts pairs with XOR<3 with {1,4}. 2^1=3 (not less than 3), 2^4=6>3, so 0. Total count is 0+0+0=0, but careful: the code counts pairs less than limit, so XOR<3 means XOR<3, not <=3.

2. Step 2: Adjust for less than limit (3) meaning XOR values 0,1,2

   Pairs: (1,4)=5>3 no, (1,2)=3 not less than 3 no, (4,2)=6 no. So count is 0. But code counts pairs as we insert, so final result is 0.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Code counts pairs with XOR < limit, result is 0 for limit=3 [OK]

Hint: XOR less than limit excludes pairs equal to limit [OK]

Common Mistakes:

• Counting pairs with XOR <= limit instead of < limit
• Off-by-one in bit traversal
• Miscounting pairs before insertion

3. Consider the following Python code implementing the optimal StreamChecker. Given the words ["cd", "f", "kl"], what is the return value of the query sequence: query('a'), query('b'), query('c'), query('d')? Specifically, what does query('d') return?

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

class StreamChecker:
    def __init__(self, words):
        self.root = TrieNode()
        self.max_len = max(len(w) for w in words)
        self.stream = []
        for word in words:
            node = self.root
            for ch in reversed(word):
                if ch not in node.children:
                    node.children[ch] = TrieNode()
                node = node.children[ch]
            node.is_word = True

    def query(self, letter):
        self.stream.append(letter)
        if len(self.stream) > self.max_len:
            self.stream.pop(0)
        node = self.root
        for ch in reversed(self.stream):
            if ch not in node.children:
                return False
            node = node.children[ch]
            if node.is_word:
                return True
        return False

sc = StreamChecker(["cd", "f", "kl"])
print(sc.query('a'))
print(sc.query('b'))
print(sc.query('c'))
print(sc.query('d'))

easy

A. False

B. True

C. Raises an exception

D. None

Solution

1. Step 1: Trace the stream buffer after queries

   After queries 'a', 'b', 'c', 'd', the stream buffer contains ['a','b','c','d'], but max_len=2, so oldest letters are popped. After 'c', stream=['b','c'], after 'd', stream=['c','d'].

2. Step 2: Traverse trie with reversed stream

   For query('d'), reversed stream is ['d','c']. Trie has reversed words: 'dc' for 'cd'. Traversing 'd' then 'c' hits is_word=True at 'c' node, so returns True. However, the query sequence is query('a'), query('b'), query('c'), query('d'). The query('c') returns False because 'c' alone is not a word. The query('d') returns True because 'cd' is in the dictionary and the stream buffer contains ['c','d'].

3. Step 3: Check query('d') return value

   Since the query('d') returns True, the correct answer is True.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Stream buffer limited to max word length matches 'cd' suffix [OK]

Hint: Stream buffer limited to max word length [OK]

Common Mistakes:

• Not limiting stream buffer size
• Not reversing words in trie
• Returning false too early

4. Consider the following buggy insert method for MapSum. Which line contains the subtle bug that causes incorrect sum queries after updating an existing key's value?

medium

A. Line where root node sum update is commented out

B. Line where delta is computed

C. Line where map[key] is updated

D. Line where child node sum is updated

Solution

1. Step 1: Understand delta and map update

   Delta correctly computes difference; map updated correctly.

2. Step 2: Identify missing root sum update

   Root node sum update is commented out, so total sums are stale, causing incorrect sum queries.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Root sum must be updated to keep prefix sums accurate [OK]

Hint: Root sum update is critical for correct prefix sums [OK]

Common Mistakes:

• Forgetting root sum update
• Updating map incorrectly
• Misplacing child sum updates

5. The following code attempts to implement the optimal StreamChecker. Identify the single line that contains a subtle bug that can cause incorrect results or inefficiency.

class StreamChecker:
    def __init__(self, words):
        self.root = TrieNode()
        self.max_len = max(len(w) for w in words)
        self.stream = []
        for word in words:
            node = self.root
            for ch in word:  # Bug here: words not reversed
                if ch not in node.children:
                    node.children[ch] = TrieNode()
                node = node.children[ch]
            node.is_word = True

    def query(self, letter):
        self.stream.append(letter)
        if len(self.stream) > self.max_len:
            self.stream.pop(0)
        node = self.root
        for ch in reversed(self.stream):
            if ch not in node.children:
                return False
            node = node.children[ch]
            if node.is_word:
                return True
        return False

medium

A. Line: for ch in word:

B. Line: if len(self.stream) > self.max_len:

C. Line: for ch in reversed(self.stream):

D. Line: if node.is_word:

Solution

1. Step 1: Identify how trie is built

   The code inserts words in forward order instead of reversed order, which breaks suffix matching logic.

2. Step 2: Understand impact on query

   Query traverses reversed stream, expecting reversed trie. Since trie is built forward, traversal fails to find matches.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Reversing words during trie build is essential for suffix queries [OK]

Hint: Trie must be built with reversed words for suffix matching [OK]

Common Mistakes:

• Not reversing words when building trie
• Not limiting stream buffer
• Returning false too early