Word Search II - Backtracking Trie - Leetcode 212 - Python 

🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤

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 .

The most enlightening moment for me was 4:40 : "Either you have heard of this data structure or you haven't". So true!

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

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 ```

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

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

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

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.

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

Man, i was SO close to getting the solution on this one, i spent maybe an hour on it. After I do all of the backtracking problems i'll return to this one and try to solve it on my own again, I was thinking about this one for hours. great video, thanks for all of the resources you've put out there!

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

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

Does it make sense to put the add word method in the TrieNode class since it is only called from the root node vs putting it in the solution class. This should have a lower memory footprint as addWord method is instantiated every time a TrieNode is created rather than once when addWord is called to create the prefix tree.

Awesome explanation! Thank you ...

love your videos so much! Please upload more!! So helpful.

It was for me a last problem from NeetCode 150 list Thanks a lot for that journey. It was sometimes frustrating, but rewarding in the end.

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.

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.

we can also add a another base case if len(res)>=len(words): return as there is no point in further iteration after finding all the words.

Good explanation as always

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

Beautiful !

Thanks you made it very simple

I was still getting TLE even after implementing the pruning. I found an optimization that finally made my solution go through, with very fast runtime. The idea is to remove all words that could not possibly be constructed by our board via letter-adjacencies. At the beginning of the findWords function, make a dictionary of sets called `adjacencies`. Each element of this dictionary represents all the letters which are adjacent to a given letter, i.e. adjacencies[ 'a' ] = { ' b' , 'c' } means that the only letters which border an 'a' are 'b' and 'c'. Then make a function which checks if a given word can be constructed from the board. Go through each character in the word (excluding the last one), and check if the character in front of it can be reached from it, i.e. if w[i+1] is in adjacencies[w[i]]. Run this function on every word in the list. If a word cannot be created by our board, we simply don't include it.

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!

optimization: 1. whenever you add a word, you can set the isword to None, then can set res as a list, shouldn't have duplicates 2. visit is not needed, set the board value to None before going to the next depth

God bless you! Backtracking, dfs and even trie. This is way high profile.

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

Nice explanation, I implemented using a trie in the board, but I came to your video to see what I was doing wrong hehehe. In ruby I needed to remove the word from the trie when found and the runtime was 208ms. I needed to track the parent node in each node so I can reverse remove.

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

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 len(t_node.children[ch].children) > 0: # has children return else: del t_node.children[ch]

If anybody is wondering why word and node are not reversed/popped just like visited set, it is because their states are maintained in the stack frames itself. we do it explicitly for sets, because its a reference and the value keeps changing throughout the calls and the states are not maintained. But for node and string, when you return back after a recursive call, state will be maintained as soon as you enter that local function frame.

you could technically prune the part of the tree once a word is found?

Thanks!!

Instead of using a trie DS, Can we use hash set to store the input words and run the dfs algorithm to check if the word exists in the hashset in every recursive call (searching for a word in hashset time complexity is O(1))? Please let me know the cons of using this approach.

Tried this same code...im getting time limit exceeeded....what should i do?

Thanks! Just a note that a straight translation to CPP won't work. I got TLE out of this. You need to get rid of visited set and the result set and do what " Leet coder Landon" said in the comment

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!

excellent video.

Hi Sir! Could you explain the time and space complexity of this? I use exact code like you wrote, now sometimes on leetcode it will get time limit exceed, do you have any solution for optimizing the time complexity? Thank you!

help... 2022 dfs with trie is timing out on leetcode

Whats the time /space complexity for this Problem ?

Did he mention the time complexity of his solution like he did for the brute force solution at the beginning? I didn't see it

U a God

this need and improvement facts. this code will give you Time limit exceded

Getting Time Limit Exceeded error. It is my first time facing error in your solution. Code runs for my own test cases, but for overall encounters TLE. Still your video is very helpful to understand this question and approaches. Leetcode solution has additional step of removing nodes from Trie if it was leaf and part of a word, to keep reducing size of Trie, maybe that's the reason of TLE. Your channel is awesome, man. I have been learning so much from your videos in a simple and easy manner. Have a good day!

The complexity sounds like O(n*m*x*y), where n is num of words, m is the max num of each word, and we do 4 dfs with visitset on the matrix, so we again search all matrix (size x*y). Couldn't we save for each subword a hashmap of the least node (word), so we could search from it further?

Nice solution with noodle code

I implemented the pruning by adding a parent variable and val variable to TrieNode: class TrieNode: def __init__(self): self.children = {} self.parent = -1 self.isWord = False self.val = '' def addWord(self, word): cur = self for c in word: if c not in cur.children: cur.children[c] = TrieNode() cur.children[c].parent = cur cur.children[c].val = c cur = cur.children[c] cur.isWord = True def pruneWord(self): cur = self while len(cur.children) == 0 and cur.parent != -1: par = cur.parent del par.children[cur.val] cur = par 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 (r,c) in visit or board[r][c] not in node.children: return visit.add((r,c)) node = node.children[board[r][c]] word += board[r][c] if node.isWord: res.append(word) node.isWord = False node.pruneWord() 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 i in range(ROWS): for j in range(COLS): dfs(i, j, root, "") return res

funny moment at 4.40. "Either you have heard of this data structure before or you have not". No way :)

Great explanation as always. Could you please please do one soon on the Egg Dropping and Cherry Pickup?

I have a question regarding the backtracking/recursion. Do we not need to pass in current vistited set as parameters to the function? why or why not??

I wonder what does “ref” mean in Java solution. I found the variable “ref” defined in Trie class.

Thanks for the great solution and explanation, but I'm getting TLE with this code as of April 2022

This same solution in C++ is giving me TLE. I even changed the visited set to an unordered_map and still cannot clear the TLE.

This is a heavy algorithm, like very complex, damn

Here is a simple variation of this solution that doesn't get TLE on LC. Don't start the DFS unless it could lead to a solution, and maintain the word at the last character's Trie Node so we don't need to maintain a local word list. Also, once we find a word we can reset TrieNode.word to "" so that word won't be looked for again. class TrieNode: def __init__(self): self.children = {} self.word = "" def addWord(self, word): root = self for c in word: if c not in root.children: root.children[c] = TrieNode() root = root.children[c] root.word = word class Solution: def findWords(self, board: List[List[str]], words: List[str]) -> List[str]: root = TrieNode() for word in words: root.addWord(word) ROWS, COLS = len(board), len(board[0]) res, visited = set(), set() def dfs(r, c, node): if r < 0 or r >= ROWS or c < 0 or c >= COLS or (r, c) in visited or board[r][c] not in node.children: return if node.children[board[r][c]].word: res.add(node.children[board[r][c]].word) node.children[board[r][c]].word = "" visited.add((r, c)) node = node.children[board[r][c]] dfs(r + 1, c, node) dfs(r - 1, c, node) dfs(r, c + 1, node) dfs(r, c - 1, node) visited.remove((r, c)) for r in range(ROWS): for c in range(COLS): if board[r][c] in root.children: dfs(r, c, root) return list(res)

Can't seem to get it to pass the last test case :/

The time limit on this problem is so trash I came up with a solution similar to the video, and I have to do almost every possible optimization for over an hour to make it get accepted.

How about converting the matrix to Trie and searching for words?

it says Time Limit Exceeded for similar java solution!

I did this in C++ and even after adding a remove function to the Trie class and getting rid of words i've already found, It's going over time limit.

it won't pass the test case for "oa" and "oaa"

One potential optimization you can make is to use a prefix tree (Trie) to store the words instead of checking for each word individually.

Great video, but there's now some failing test cases 44/62

is it 4^(length of total characters in WORDS array which in worst case might grow to m*n)?? This is what you meant??

why there could be duplicates?

How u come up with all of this solution ideas bro? it took me like 20 minutes to realise why your code works 🤣

This is quite hard problem

Is it just me, or does anyone else also get a Time Limit Exceeded error for this solution? Any possible fixes so it can run within the given time limit?

Neet explanation

I solved this problem by myself, but it's slow to pass the test cases in leetcode

This gives time limit exceeded error.

i did the trie for the matrix instead of given words lol

What's the complexity in this problem?

How to prune based on your code? This gets TLE now.

you should redo this one

inputs are after 4 a b c d f e f g t e r r a b i j output wants to come as [(0,0),(1,0),(2,0),(2,1),(2,2)] different inputs are search 4 s e a c r c c c h e e e h e e e output wants to come as "no such word is there" how will do this in python pls explain

Got a TLE? Neet has already posted a solution for it on the site: class TrieNode: def __init__(self): self.children = {} self.isWord = False self.refs = 0 def addWord(self, word): cur = self cur.refs += 1 for c in word: if c not in cur.children: cur.children[c] = TrieNode() cur = cur.children[c] cur.refs += 1 cur.isWord = True def removeWord(self, word): cur = self cur.refs -= 1 for c in word: if c in cur.children: cur = cur.children[c] cur.refs -= 1 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(), set() def dfs(r, c, node, word): if ( r not in range(ROWS) or c not in range(COLS) or board[r][c] not in node.children or node.children[board[r][c]].refs < 1 or (r, c) in visit ): return visit.add((r, c)) node = node.children[board[r][c]] word += board[r][c] if node.isWord: node.isWord = False res.add(word) root.removeWord(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 list(res) @NeetCode, it would be great if you could explain this a bit more. :-)

14:41, in line 7, Why cur should be "self" not "TrieNode()"? In line 10, why cur.children[c] should be "TrieNode()"? not "self"? I am so confused about that.

leetcode is finicky and won't accept the same solution written in PHP: Time Limit Exceeded.

horray

I tried many ways, still can't pass all the test😭

Bouncer

this solution will be TLE in 2022

apec not found? try apex

If you are getting Time Limit Exceeded, try this. (As of 2022 July) if curr.isWord: res.append(word) curr.isWord=False if not curr.children: node.children.pop(board[r][c],None) (I also used a list instead of a set for res, so you can just return res instead of list(res). Setting curr.isWord = False takes care of duplicates)

Did anyone else get an index out of range error for the if statement for the dfs basecase?

For Passing last testcase, we need to prune the word if children of that word is zero after the dfs calls. example: if(child.isCompleteWord) { presentWords.add(word); } dfs(i + 1, j, board, child, word, visited, presentWords); dfs(i - 1, j, board, child, word, visited, presentWords); dfs(i, j + 1, board, child, word, visited, presentWords); dfs(i, j - 1, board, child, word, visited, presentWords); // prune logic after exploring all paths from i and j if(child.isCompleteWord) { child.isCompleteWord = false; if(child.children.size() == 0) { trie.children.remove(currentChar); } } complete code: class Node { HashMap children; boolean isCompleteWord; public Node() { children = new HashMap(); isCompleteWord = false; } public void insert(String word) { if(word.isEmpty()) { isCompleteWord = true; return; } char startChar = word.charAt(0); String remaining = word.substring(1); if(children.containsKey(startChar)) { children.get(startChar).insert(remaining); } else { Node child = new Node(); children.put(startChar, child); child.insert(remaining); } } public String toString() { return "{ children: " + children + " , isCompleteWord: " + isCompleteWord + " }"; } } class Solution { public List findWords(char[][] board, String[] words) { Node trie = buildTrie(words); // System.out.println(trie.toString()); List presentWords = new ArrayList(); HashSet visited = new HashSet(); for(int i = 0; i < board.length; i++) { for(int j = 0; j < board[0].length; j++) { dfs(i, j, board, trie, "", visited, presentWords); } } return presentWords; } private void dfs(int i, int j, char[][] board, Node trie, String word, HashSet visited, List presentWords) { String key = i + "|" + j; if(visited.contains(key)) { return ; } int row = board.length; int col = board[0].length; if(i >= row || i < 0 || j >= col || j < 0) { return; } char currentChar = board[i][j]; if(trie.children.containsKey(currentChar)) { visited.add(key); Node child = trie.children.get(currentChar); word = word + "" + currentChar; if(child.isCompleteWord) { presentWords.add(word); } dfs(i + 1, j, board, child, word, visited, presentWords); dfs(i - 1, j, board, child, word, visited, presentWords); dfs(i, j + 1, board, child, word, visited, presentWords); dfs(i, j - 1, board, child, word, visited, presentWords); if(child.isCompleteWord) { child.isCompleteWord = false; if(child.children.size() == 0) { trie.children.remove(currentChar); } } visited.remove(key); } } private Node buildTrie(String[] words) { Node trie = new Node(); for(String word: words) { trie.insert(word); } return trie; } }

For people who got TLE: You could try instead of storing visit set, mark path with '#' class TrieNode: def __init__(self): self.children = {} self.endOfWord = 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.endOfWord = True 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 = set() def dfs(r, c, node, word): if r < 0 or c < 0 or r == rows or c == cols or board[r][c] == '#' or board[r][c] not in node.children: return False node = node.children[board[r][c]] word += board[r][c] tmp = board[r][c] board[r][c] = '#' if node.endOfWord: res.add(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) board[r][c] = tmp for r in range(rows): for c in range(cols): dfs(r, c, root, '') return list(res)

Just small modification to avoid TLE ####################### 1. Fasle the EndOfWord 2. Adding num_of_word variable class TrieNode: def __init__(self): self.children = {} self.EndOfWord = False def add_word(self, word): cur = self for c in word: if c not in cur.children: cur.children[c]=TrieNode() cur = cur.children[c] cur.EndOfWord = True class Solution: def __init__(self): self.num_of_words = 0 def findWords(self, board: List[List[str]], words: List[str]) -> List[str]: self.num_of_words = len(words) root = TrieNode() for word in words: root.add_word(word) res, visit = [], set() def dfs(x, y, word, node): if x=len(board[0]) or board[x][y] not in node.children or (x,y) in visit or self.num_of_words == 0: return visit.add((x,y)) node = node.children[board[x][y]] word+=board[x][y] if node.EndOfWord: res.append(word) node.EndOfWord = False #################################### self.num_of_words-=1 ############################### dfs(x+1, y, word, node) dfs(x, y+1, word, node) dfs(x-1, y, word, node) dfs(x, y-1, word, node) visit.remove((x,y)) for i in range(len(board)): for j in range(len(board[0])): dfs(i, j, "", root) return res

class TrieNode: def __init__(self): self.children = {} self.is_end = False class Trie: def __init__(self,root_node): self.root = root_node def insert_word_into_trie(self,word): curr_node = self.root for char in word: if char not in curr_node.children: curr_node.children[char] = TrieNode() curr_node = curr_node.children[char] curr_node.is_end = True def prune_word(self, word): curr_node = self.root stack = [] for char in word: stack.append(curr_node) curr_node = curr_node.children[char] curr_node.is_word = False for trie_node, char in reversed(list(zip(stack, word))): if len(trie_node.children[char].children) > 0: # has children return else: del trie_node.children[char] class Solution: def findWords(self, grid: List[List[str]], words: List[str]) -> List[str]: root_node = TrieNode() trie = Trie(root_node) for word in words: trie.insert_word_into_trie(word) ROWS,COLS = len(grid), len(grid[0]) visit = set() res = [] directions = [(0,1),(0,-1),(-1,0),(1,0)] def dfs(r,c,pref_word,curr_node): if r < 0 or c < 0 or r == ROWS or c == COLS or grid[r][c] not in curr_node.children or (r,c) in visit: return visit.add((r,c)) curr_node = curr_node.children[grid[r][c]] pref_word += grid[r][c] if curr_node.is_end: res.append(pref_word) trie.prune_word(pref_word) for dr, dc in directions: dfs(r+dr,c+dc,pref_word,curr_node) visit.remove((r,c)) for r in range(ROWS): for c in range(COLS): dfs(r,c,"",root_node) return list(set(res))

function dfs() { .... (r < 0 || c < 0) || (r === ROWS || c === COLS) || ( visit.has(`${r},${c}`)) || (! (board[r][c] in node.children) ) || (res.size === words.length) //