Word Search II - Backtracking Trie - Leetcode 212 - Python

0:00 - Read the problem
5:06 - Drawing Explanation
12:32 - Coding Explanation

leetcode 212

#trie #prefix #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[amitupadhyay]

I faced this question in Uber interview. For fresh grad, they go with the hard problem in first round itself. Further, though I gave DFS solution they wanted trie one .

[SOMESHKHANDELIA]

The most enlightening moment for me was 4:40 :

"Either you have heard of this data structure or you haven't".

So true!

[PippyPappyPatterson]

Neet's solution as of June 2022 TLEs.

To pass the Leetcode test cases you have to prune words from the prefix tree after you've found them. Here is the same as his solution with the addition of a `removeWord` method:

```python
class TrieNode:
def __init__(self):
self.children = {}
self.isWord = False

def addWord(self, word):
cur = self
for c in word:
if c not in cur.children:
cur.children[c] = TrieNode()
cur = cur.children[c]
cur.isWord = True

def pruneWord(self, word) -> None:
cur: TrieNode = self
nodeAndChildKey: list[tuple[TrieNode, str]] = []
for char in word:
nodeAndChildKey.append((cur, char))
cur = cur.children[char]

for parentNode, childKey in reversed(nodeAndChildKey):
targetNode = parentNode.children[childKey]
if len(targetNode.children) == 0:
del parentNode.children[childKey]
else:
return


class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
root = TrieNode()
for w in words:
root.addWord(w)

ROWS, COLS = len(board), len(board[0])
res, visit = [], set()

def dfs(r, c, node, word):
if (r < 0 or c < 0 or
r == ROWS or c == COLS or
board[r][c] not in node.children or (r, c) in visit):
return

visit.add((r, c))
node = node.children[board[r][c]]
word += board[r][c]
if node.isWord:
res.append(word)
node.isWord = False
root.pruneWord(word)

dfs(r + 1, c, node, word)
dfs(r - 1, c, node, word)
dfs(r, c + 1, node, word)
dfs(r, c - 1, node, word)
visit.remove((r, c))

for r in range(ROWS):
for c in range(COLS):
dfs(r, c, root, "")

return res
```

[rohanramani]

How tf am I supposed to solve this in a 35 min interview lol

[tayjen]

That's a good explanation, thank you man. However I have to notice something. On your site, the Trie topic comes before Backtracking and for people who solve problems in such an orderly way, it would be nice to have it sorted out a little.

[cansuyanik]

19:54 instead of doing this, node.isWord can be set to false after adding word to res in the dfs function.

[ronsaxeditz]

You're a life saver, these videos are amazing!

[DragonStoneCreations]

Initially, I thought of building a Trie for the Maze and was sweating... but u just built a Trie on the words and made it like a piece of cake :D

[boluo]

i always look for your leetcode videos 😄 Thanks for making these great videos!

[gabchen]

This was my approach for removing the word from Trie to overcome Time Limit Exceeded on python:
[... in Trie class ...]:
def removeWord(self, word):
cur = self
for c in word:
if len(cur.child[c].child) == 0:
del cur.child[c]
return
else:
cur = cur.child[c]

[... in dfs function ...]:
if node.end:
res.add(word)
# this is optimization, remove the word after it has been found
node.end = False
root.removeWord(word)


hope this helps!

[Andres-xrcb]

How would you do this problem with an iterative approach and not a recursive one?

[shashikiran]

The actual Optimization is that, we need to keep track of how many words is prefixed from a particular Node in the Trie. This is done during the insertion of words. Now whenever we find a word during the search, we should recursively decrement the count of that node and all the nodes directly above it till root. When this count reaches 0 at any particular node, we should prune that node branch. This would be a lot more optimized.
But yes, the time complexity would not decrease. It would only be efficient in this particular problem.

[joshpark]

3:33 isn't the time complexity for the naive solution wmn4^s where s is the longest word in the words array? Since at max we're going to traverse s amount of letters in 4 directions

[overcharged]

in your site this comes before backtracking, is hard to follow up or solve without backtracking knowledge, good explanation though :)

[MichaelShingo]

came back to this after doing Backtracking and Grid-graph problems in Blind 75 and it makes so much more sense

[GopalKumar-lxhn]

We can get TLE, better to mark node.isWord = false while adding the word in res. Bonus, by this we can use list directly instead of set, as we guaranty, all the words occur only once.

[leok]

A way to solve the TLE is to add a prune method to the TrieNode class. The idea is when you find a word you delete it from the tree in order to optimize the time complexity.
def prune(self, word):
curr = self
stack = []

for ch in word:
stack.append(curr)
curr = curr.children[ch]
curr.is_word = False

for t_node, ch in reversed(list(zip(stack, word))):
if > 0: # has children
return
else:
del t_node.children[ch]

[telnet]

final video on your playlist, thank you for this amazing content.

[WhisperingWalnuts]

this solution is timing out now since the best solution in leetcode have done a stronger tweaks. Thats dumb on leetcode! But, thanks a lot for this video!

[habalgarmin]

Your solution really helped me to fix TLE. Shame on me, I couldn't come up with the right solution on my own =(