Palindrome Pairs

▶

Steps

setup

Initialize Trie Root

Create the root node of the trie with empty children, index -1, and empty palindrome suffix list.

💡 The root node is the starting point for all insertions and searches in the trie.

Line:

root = TrieNode()

💡 A single root node is needed to build the trie structure for all reversed words.

insert

Insert reversed 'abcd' (word 0) into trie, char 'd'

Start inserting reversed 'abcd' which is 'dcba'. Insert character 'd' at root's children.

💡 Inserting reversed words allows matching suffixes of original words during search.

Line:

for i, ch in enumerate(reversed(word)):
    if ch not in node.children:
        node.children[ch] = TrieNode()

💡 Trie grows by adding nodes for characters not yet present, building reversed word paths.

insert

Insert reversed 'abcd' (word 0), char 'c'

Insert next character 'c' under node for 'd'. Check if prefix is palindrome for suffix tracking.

💡 Checking palindrome prefixes helps store indices for suffixes that form palindromes.

Line:

if is_palindrome(word[:len(word)-i]):
    node.palindrome_suffixes.append(index)

💡 Only palindrome prefixes cause suffix indices to be stored for later pair matching.

insert

Insert reversed 'abcd' (word 0), char 'b'

Insert character 'b' under node for 'c'. Check palindrome prefix for suffix tracking.

💡 Continuing insertion, palindrome checks ensure suffix indices are stored correctly.

Line:

if is_palindrome(word[:len(word)-i]):
    node.palindrome_suffixes.append(index)

💡 Only palindrome prefixes add indices to suffix lists, pruning unnecessary pairs.

insert

Insert reversed 'abcd' (word 0), char 'a' and mark index

Insert last character 'a' under node 'b'. Mark this node's index as 0 and add index to palindrome_suffixes.

💡 Marking index at end node identifies complete reversed word for matching during search.

Line:

node.index = index
node.palindrome_suffixes.append(index)

💡 End nodes store word indices and palindrome suffix info for efficient pair detection.

insert

Insert reversed 'dcba' (word 1), char 'a'

Start inserting reversed 'dcba' which is 'abcd'. Insert character 'a' at root's children.

💡 Inserting next reversed word builds trie branches for matching prefixes.

Line:

for i, ch in enumerate(reversed(word)):
    if ch not in node.children:
        node.children[ch] = TrieNode()

💡 Trie branches grow as new reversed words introduce new prefixes.

insert

Insert reversed 'dcba' (word 1), char 'b'

Insert character 'b' under node 'a'. Check palindrome prefix for suffix tracking.

💡 Palindrome prefix checks continue to identify suffix indices.

Line:

if is_palindrome(word[:len(word)-i]):
    node.palindrome_suffixes.append(index)

💡 Only palindrome prefixes add indices to suffix lists.

insert

Insert reversed 'dcba' (word 1), char 'c'

Insert character 'c' under node 'b'. Check palindrome prefix for suffix tracking.

💡 Continuing insertion with palindrome suffix checks.

Line:

if is_palindrome(word[:len(word)-i]):
    node.palindrome_suffixes.append(index)

💡 Only palindrome prefixes add indices to suffix lists.

insert

Insert reversed 'dcba' (word 1), char 'd' and mark index

Insert last character 'd' under node 'c'. Mark node index as 1 and add to palindrome_suffixes.

💡 Marking end node with word index for matching during search.

Line:

node.index = index
node.palindrome_suffixes.append(index)

💡 End nodes identify complete reversed words for pair matching.

search

Search for palindrome pairs with word 'abcd' (index 0), char 'a'

Start searching trie with 'abcd'. At root, check if node index is valid and if suffix 'abcd' is palindrome.

💡 Searching tries to find matching reversed prefixes and palindrome suffixes.

Line:

if node.index >= 0 and node.index != index and is_palindrome(word[i:]):
    res.append([index, node.index])

💡 Pairs are added only when node index differs and suffix is palindrome.

search

Search with word 'abcd' (index 0), char 'b'

Move to child node for 'a'. Check if node index valid and suffix 'bcd' palindrome.

💡 Checking palindrome suffixes at each step helps find pairs early.

Line:

if node.index >= 0 and node.index != index and is_palindrome(word[i:]):
    res.append([index, node.index])

💡 No pair found yet, continue traversal.

search

Search with word 'abcd' (index 0), char 'c'

Move to child node for 'b'. Check if node index valid and suffix 'cd' palindrome.

💡 Continuing search to find matching reversed prefixes.

Line:

if node.index >= 0 and node.index != index and is_palindrome(word[i:]):
    res.append([index, node.index])

💡 No pair found yet, continue traversal.

search

Search with word 'abcd' (index 0), char 'd'

Move to child node for 'c'. Check if node index valid and suffix 'd' palindrome.

💡 At last character, check for palindrome suffixes to add pairs.

Line:

if node.index >= 0 and node.index != index and is_palindrome(word[i:]):
    res.append([index, node.index])

💡 Found palindrome pair by matching reversed prefix and palindrome suffix.

search

Add pairs from palindrome_suffixes at node after full traversal of 'abcd'

After full traversal, add pairs from palindrome_suffixes stored at current node excluding current word index.

💡 Palindrome suffix indices at end node represent words that form palindrome pairs.

Line:

for j in node.palindrome_suffixes:
    if j != index:
        res.append([index, j])

💡 Palindrome suffixes at end node help find pairs with empty suffix.

search

Search for palindrome pairs with word 'dcba' (index 1), char 'd'

Start searching trie with 'dcba'. At root, check if node index valid and suffix 'dcba' palindrome.

💡 Searching for pairs with second word to find reverse pairs.

Line:

if node.index >= 0 and node.index != index and is_palindrome(word[i:]):
    res.append([index, node.index])

💡 Search continues to find matching reversed prefixes.

search

Search with word 'dcba' (index 1), char 'c'

Move to child node for 'd'. Check if node index valid and suffix 'cba' palindrome.

💡 Continuing search for matching reversed prefixes.

Line:

if node.index >= 0 and node.index != index and is_palindrome(word[i:]):
    res.append([index, node.index])

💡 No pair found yet, continue traversal.

search

Search with word 'dcba' (index 1), char 'b'

Move to child node for 'c'. Check if node index valid and suffix 'ba' palindrome.

💡 Continuing search for palindrome pairs.

Line:

if node.index >= 0 and node.index != index and is_palindrome(word[i:]):
    res.append([index, node.index])

💡 No pair found yet, continue traversal.

search

Search with word 'dcba' (index 1), char 'a'

Move to child node for 'b'. Check if node index valid and suffix 'a' palindrome.

💡 At last character, check for palindrome suffixes to add pairs.

Line:

if node.index >= 0 and node.index != index and is_palindrome(word[i:]):
    res.append([index, node.index])

💡 Found palindrome pair by matching reversed prefix and palindrome suffix.

search

Add pairs from palindrome_suffixes at node after full traversal of 'dcba'

After full traversal, add pairs from palindrome_suffixes stored at current node excluding current word index.

💡 Palindrome suffix indices at end node represent words that form palindrome pairs.

Line:

for j in node.palindrome_suffixes:
    if j != index:
        res.append([index, j])

💡 Palindrome suffixes at end node help find pairs with empty suffix.

reconstruct

Final result after processing all words

After inserting all words and searching for pairs, the final palindrome pairs are collected.

💡 The final pairs represent all palindrome pairs found by the algorithm.

Line:

return result

💡 The algorithm efficiently finds palindrome pairs using trie and palindrome suffix tracking.

class TrieNode:
    def __init__(self):
        self.children = {}  # STEP 1
        self.index = -1
        self.palindrome_suffixes = []

def is_palindrome(word):
    return word == word[::-1]

def palindromePairs(words):
    root = TrieNode()  # STEP 1

    def add_word(word, index):
        node = root
        for i, ch in enumerate(reversed(word)):
            if is_palindrome(word[:len(word)-i]):  # STEP 2-5
                node.palindrome_suffixes.append(index)
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.index = index  # STEP 5
        node.palindrome_suffixes.append(index)

    def search(word, index):
        res = []
        node = root
        for i, ch in enumerate(word):
            if node.index >= 0 and node.index != index and is_palindrome(word[i:]):  # STEP 10-19
                res.append([index, node.index])
            if ch not in node.children:
                return res
            node = node.children[ch]
        for j in node.palindrome_suffixes:
            if j != index:
                res.append([index, j])
        return res

    for i, word in enumerate(words):
        add_word(word, i)  # STEP 2-9

    result = []
    for i, word in enumerate(words):
        result.extend(search(word, i))  # STEP 10-19
    return result  # STEP 20

if __name__ == '__main__':
    words = ["abcd","dcba","lls","s","sssll"]
    print(palindromePairs(words))

📊

Palindrome Pairs - Watch the Algorithm Execute, Step by Step

Watching the trie construction and search step-by-step reveals how palindrome suffixes are used to efficiently find pairs without brute force checks.

setup

abcd

0

dcba

1

lls

2

s

3

sssll

4

Result: []

insert

node

abcd

0

dcba

1

lls

2

s

3

sssll

4

Result: []

insert

abcd

0

node

dcba

1

lls

2

s

3

sssll

4

Result: []

insert

abcd

0

dcba

1

node

lls

2

s

3

sssll

4

Result: []

insert

abcd

0

dcba

1

lls

2

node

s

3

sssll

4

Result: []

insert

node

abcd

0

dcba

1

lls

2

s

3

sssll

4

Result: []

insert

abcd

0

dcba

1

lls

2

s

3

node

sssll

4

Result: []

insert

abcd

0

dcba

1

lls

2

s

3

sssll

4

Result: []

insert

abcd

0

dcba

1

lls

2

s

3

sssll

4

Result: []

compare

node

abcd

0

dcba

1

lls

2

s

3

sssll

4

Result: []

compare

abcd

0

i

dcba

1

lls

2

s

3

node

sssll

4

Result: []

compare

abcd

0

dcba

1

i

lls

2

s

3

sssll

4

Result: []

compare

abcd

0

dcba

1

lls

2

i

s

3

sssll

4

Result: [[0,1]]

record

abcd

0

dcba

1

lls

2

s

3

sssll

4

Result: [[0,1]]

compare

node

abcd

0

dcba

1

lls

2

s

3

sssll

4

Result: [[0,1]]

compare

abcd

0

node

dcba

1

lls

2

s

3

sssll

4

Result: [[0,1]]

compare

abcd

0

dcba

1

i

lls

2

s

3

sssll

4

Result: [[0,1]]

compare

abcd

0

dcba

1

lls

2

i

s

3

sssll

4

Result: [[0,1],[1,0]]

record

abcd

0

dcba

1

lls

2

s

3

sssll

4

Result: [[0,1],[1,0]]

reconstruct

abcd

0

dcba

1

lls

2

s

3

sssll

4

Result: [[0,1],[1,0],[3,2],[2,4]]

Key Takeaways

✓ Building a trie with reversed words and storing palindrome suffix indices enables efficient palindrome pair detection.

This insight is hard to see from code alone because it involves understanding how suffix palindrome checks prune the search space.

✓ During search, checking if the remaining substring is a palindrome at nodes with valid indices reveals pairs early.

Visualizing pointer movement and palindrome checks clarifies why some pairs are found before full traversal.

✓ Palindrome suffix lists at trie nodes allow pairing words with empty suffixes or overlapping palindromes.

Seeing these lists in the trie structure helps understand how the algorithm handles complex palindrome cases.

Practice

1. You need to design a data structure that efficiently supports insertion of strings, exact search for strings, and prefix-based search queries. Which of the following data structures guarantees optimal time complexity for these operations regardless of the number of stored strings?

easy

A. Hash Set storing all strings for O(1) average search but no efficient prefix search

B. Trie (Prefix Tree) that stores characters in nodes with links to children nodes

C. Sorting all strings and using binary search for prefix queries

D. Using a balanced binary search tree keyed by entire strings

Solution

1. Step 1: Understand operation requirements

   Insertion, exact search, and prefix search must be efficient. Hash sets provide O(1) average search but cannot efficiently support prefix queries.

2. Step 2: Compare data structures

   Tries store characters in nodes allowing O(m) time for insert/search/startsWith, where m is length of word or prefix. Binary search on sorted strings is O(m log n) and BSTs do not support prefix queries efficiently.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Trie supports prefix queries in O(m) time [OK]

Hint: Tries enable prefix queries in O(m) time [OK]

Common Mistakes:

• Confusing hash sets as supporting prefix queries efficiently

2. Given the following code snippet for MapSum, after inserting keys "apple" with value 3 and "app" with value 2, what is the value of node.sum at the trie node corresponding to 'p' (the second character) after the second insert?

easy

A. 3

B. 5

C. 2

D. 0

Solution

1. Step 1: Trace insert of "apple" with value 3

   Delta = 3 - 0 = 3. Root.sum += 3 -> 3. For each character 'a','p','p','l','e', node.sum += 3. After first insert, node at second 'p' has sum 3.

2. Step 2: Trace insert of "app" with value 2

   Delta = 2 - 0 = 2. Root.sum += 2 -> 5. For 'a','p','p', node.sum += 2. Node at second 'p' sum was 3, now 3 + 2 = 5.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sum at second 'p' after both inserts is 5 [OK]

Hint: Sum accumulates delta on each insert per prefix node [OK]

Common Mistakes:

• Forgetting to add delta on second insert
• Confusing first and second 'p' nodes
• Using old value instead of delta

3. What is the time complexity of building the trie and retrieving suggestions for a searchWord of length m, given n products each of average length k, when using the trie with stored top 3 suggestions approach?

medium

A. O(m * n * k) because each prefix requires scanning all products

B. O(n * k * m) because for each character in searchWord, we traverse all products

C. O(n * k + m) because building the trie takes O(n * k) and searching takes O(m)

D. O(n + m * k) because building trie is linear in n and searching depends on k

Solution

1. Step 1: Analyze trie building complexity

   Building the trie requires inserting each of the n products of length k, so O(n * k).

2. Step 2: Analyze search complexity

   Searching for suggestions for each of the m characters in searchWord requires traversing down the trie nodes, O(m).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Trie building dominates with O(n*k), search is O(m) [OK]

Hint: Trie build is O(n*k), search is O(m) [OK]

Common Mistakes:

• Confusing brute force with trie complexity
• Multiplying m unnecessarily
• Ignoring that search is prefix traversal only

4. Suppose the problem is modified so that root words can be reused multiple times to replace multiple prefixes in a single word (e.g., 'catcat' could be replaced by 'catcat' if 'cat' is a root). Which modification to the trie-based approach correctly handles this variant?

hard

A. Use the existing shortest prefix search once per word; no change needed as reuse is irrelevant.

B. After finding the shortest prefix, continue searching the remaining suffix recursively for more prefixes to replace.

C. Modify search to find the longest prefix instead of shortest, then recursively replace the suffix with roots.

D. Replace the entire word only if it exactly matches a root; otherwise, leave it unchanged.

Solution

1. Step 1: Understand reuse requirement

   Words can be replaced by concatenations of multiple root prefixes, so partial replacements must continue recursively.

2. Step 2: Modify search logic

   After finding a shortest prefix, recursively apply the same prefix search on the remaining suffix to replace all possible prefixes.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Recursive prefix replacement handles multiple root reuse correctly [OK]

Hint: Recursively replace suffixes after shortest prefix [OK]

Common Mistakes:

• Stopping after first prefix
• Searching for longest prefix only

5. Suppose the problem changes: words can be repeated multiple times and you want the shortest unique prefix that distinguishes each occurrence (including duplicates). Which modification to the trie-based solution correctly handles this?

hard

A. Store a list of word indices at each node and find prefix unique to each index.

B. Modify frequency increments to count each occurrence separately and return prefix only if frequency equals the occurrence count.

C. No change needed; the existing frequency counts handle duplicates naturally.

D. Sort words first and compare adjacent duplicates to assign unique prefixes.

Solution

1. Step 1: Understand duplicate occurrence challenge

   Duplicates share the same prefix path and frequency counts, so frequency alone cannot distinguish occurrences.

2. Step 2: Identify solution

   Storing word indices at each node allows tracking which occurrences pass through, enabling unique prefix per occurrence.

3. Step 3: Why other options fail

   No change needed; the existing frequency counts handle duplicates naturally. ignores duplicates; B misuses frequency counts; D breaks original order and misses non-adjacent duplicates.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Tracking indices enables unique prefixes per duplicate [OK]

Hint: Frequency counts alone can't distinguish identical duplicates [OK]

Common Mistakes:

• Assuming frequency counts suffice for duplicates
• Relying on sorting only