Word Search II | LeetCode | Solution Explained in Detail

Amazon Interview Question. 212. Word Search II is a hard problem. I explain in detail how we can use the Trie/Prefix Tree & concepts from Word Search I to build the solution for this problem. We start with a revision of Word Search I and then look at observations, realizing the presence of common prefixes that can make our search easier. So, we develop the ideas of prefix trees and code that in Python3. Then we move onto looking at parallels between Word Search I and Word Search II, and we see a lot of similarities. Finally, we code that up as well. Then we do some basic setup and get this solution accepted.

Writeup (Summary + Code):

Previous references:
Word Search I

Trie/Prefix Tree

Problem link:

==================================================

Timestamps:
0:00 Introduction
0:16 Reviewing Word Search I
4:53 Word Search II problem discussion
6:24 Observations & A free tip
9:47 Part 1: Using Prefix Tree/Trie
11:56 Part 1: Coding Prefix Tree/Trie
15:33 Part 2: Extending Word Search I Logic
18:02 Part 2: Coding Extension
26:53 Final Discussion

==================================================

Stuff I use:

NOTE: These are affiliate links.
- Doesn't cost you anything
- Gives me a kickback if you buy this :)

==================================================

Follow:
#LeetCode #coding #programming #chaudhary1337

==================================================

[chaudharycodes]

If you have seen the last two video solutions, you can directly jump to 15:33. If not, don't worry! I have explained *everything* you need for this solution :)

Timestamps:
0:00 Introduction
0:16 Reviewing Word Search I
4:53 Word Search II problem discussion
6:24 Observations & A free tip
9:47 Part 1: Using Prefix Tree/Trie
11:56 Part 1: Coding Prefix Tree/Trie
15:33 Part 2: Extending Word Search I Logic
18:02 Part 2: Coding Extension
26:53 Final Discussion

Thanks!

[prashlovessamosa]

This channel is heaven to me bahiya you are awesome teacher

[Apurvsankhyadhar]

Dude, you're a blessing to us people preparing for the placement tests everyday. Please keep this daily coding challenge going on like this

[hymnish_you]

Oh, I implemented it the same way. Few catches which I want to mention:
Rather than generating words on the go like _path+c_, We can directly store word at the end in place of boolean _isEnd_ . (It saves additional space complexity of NoOfWords*WordLength).. CMIIW
And it also saves the additional *set* introduction. We can again set that word to null when we have already saved it to our answer list.

[roll]

Brilliant Explanation!! I get a lot of help from your solution videos with the catagorizion. out of curiosity how many leetcode questions did you solve?

[VivekKumar-esli]

awesome explaination. btw how did you add path+c at the same time to every sentence 23:46?

[sidheshwar]

I implemented it on my own, your last Trie and word search 1 video helped me. But the small catch is if I use for loop to do the up, down, left, right recursion it throws TLE. But if i simple right down those four lines it works! Any idea why that happens.

This lead to TLE:
class Node:
def __init__(self, c, end=False):
self.child = {}
self.c = c
self.end = end

class Trie:
def __init__(self):
self.root = Node("/")

def insert(self, word):
cur = self.root
for c in word:
if c not in cur.child: cur.child[c] = Node(c)
cur = cur.child[c]
cur.end = True

class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
lookup = Trie()
for w in words:
lookup.insert(w)

def dfs(r, c, cur, word):
if not (0<=r<n and 0<=c<m): return
w = board[r][c]
if w not in cur.child: return
if cur.child[w].end:
ans.add(word+w)
board[r][c] = " "
path = [(-1, 0), (1, 0), (0, -1), (0, 1)]
[dfs(r+x, c+y, cur.child[w], word+w) for x, y in path]
board[r][c] = w

n = len(board)
m = len(board[0])
ans = set()

for r in range(n):
for c in range(m):
dfs(r, c, lookup.root, "")

return ans

Whereas This works:

class Node:
def __init__(self, c, end=False):
self.child = {}
self.c = c
self.end = end

class Trie:
def __init__(self):
self.root = Node("/")

def insert(self, word):
cur = self.root
for c in word:
if c not in cur.child: cur.child[c] = Node(c)
cur = cur.child[c]
cur.end = True

class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
lookup = Trie()
for w in words:
lookup.insert(w)

def dfs(r, c, cur, word):
if not (0<=r<n and 0<=c<m): return
w = board[r][c]
if w not in cur.child: return
if cur.child[w].end:
ans.add(word+w)
board[r][c] = " "
path = [(-1, 0), (1, 0), (0, -1), (0, 1)]
dfs(r+1, c, cur.child[w], word+w)
dfs(r-1, c, cur.child[w], word+w)
dfs(r, c+1, cur.child[w], word+w)
dfs(r, c-1, cur.child[w], word+w)

board[r][c] = w

n = len(board)
m = len(board[0])
ans = set()

for r in range(n):
for c in range(m):
dfs(r, c, lookup.root, "")

return ans