Word Search II | Leetcode 212

.
.
.
Happy Programming !!! Pep it up 😍🤩
.
.
.
#pepcoding #code #coder #codinglife #programming #coding #java #freeresources #datastrucutres #pepcode #competitive #competitiveprogramming #softwareengineer #engineering #engineer
Topic: #WordSearchII #Leetcode212

Question Statement:
1. Given an m x n board of characters and a list of strings words, return all words present on the board.
2. Word must be made from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

You can return word's in any order.

Used #DataStructure: #Trie #Array #String #ArrayList #HashSet

--------------------------------------------------------------

Linked Questions:

--------------------------------------------------------------

Smimilar Questions:

---------------------------------------------------------------

----------------------------------------------------------------

#Trie #Array #String #ArrayList #HashSet # Leetcode212

[arpitmani]

Leetcode has updated the testcases hence the the optimisation(deleting nodes by keeping count) will not work now.
Submit the code without deleting node and keeping count(i.e code till 47:24).
Otherwise nice explanation.

[subhamoyburman]

Excellent explanation - the prerequisite for this will be the implementation of Trie and Backtracking. Not sure whether in the interview in a single round, one will be able to cover Trie implementation + Dry run + code of this problem. But an excellent problem that indeed brings all the concepts of DFS, Backtracking, Trie together.

[dochimekashiariri]

1:00:12 that caught me by surprise in background😂

[sushyyyyyyyy]

Worth the watching 1 hr long solution, so much learning! thnakyou pepcoding & sir!!!

[ashutoshkumar]

Good luck getting an optimal solution and coding it in 45 min if you haven't solved it before

[pranaynagpure]

the child.count ==0 condition should be inside line 47(child.str != null) condition because it will delete all the child node

[derilraju]

Python code on LC 212

class TrieNode:
def __init__(self, val=None, parent=None):
self.children = {}
self.endWord = ""
self.val = val
self.parent = parent

class Solution:

def trieInsert(self, root, word):
cur = root
for ch in word:
if ch not in cur.children:
cur.children[ch] = TrieNode(val=ch, parent=cur)
cur = cur.children[ch]

cur.endWord = word

def triePrune(self, node):
child = node
parent = child.parent

while parent and len(child.children) == 0:
del parent.children[child.val]
child = parent
parent = parent.parent

def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:

m, n = len(board), len(board[0])
visited = [[False for j in range(n)] for i in range(m) ]
ans = []

root = TrieNode()

for word in words:
self.trieInsert(root, word)


for i in range(m):
for j in range(n):
self.dfs(i, j, visited, board, m, n, root, ans)

return ans

def dfs(self, i, j, visited, board, m, n, root, ans):
if i<0 or j<0 or i>=m or j>=n or visited[i][j]:
return

if not board[i][j] in root.children:
return

child = root.children[board[i][j]]
if child.endWord != "":
ans.append(child.endWord)
child.endWord = ""
self.triePrune(child)

if len(child.children) == 0:
return

visited[i][j] = True
self.dfs(i+1, j, visited, board, m, n, child, ans)
self.dfs(i, j+1, visited, board, m, n, child, ans)
self.dfs(i-1, j, visited, board, m, n, child, ans)
self.dfs(i, j-1, visited, board, m, n, child, ans)
visited[i][j] = False

[debangikbose]

Sir it would be really helpful if possible u can provide this video and the upcoming videos in level 1 or level 2 playlist as per its level so that we can access the resources in an order

[shrutiemu]

Can you please share the code for the same since pepcoding site is not available

[thekumarpriyansh]

Accepted 3 ms 39.2 MB java
Accepted 134 ms 39.4 MB java
This is difference with and without optimisation. Thank you sir. Awesome explanation.

[umanggupta]

Deleting nodes by tracking count of children is pretty awesome

[shamshadhussainsaifi]

Ur video is very helpful .I request do not make lengthy video, plz try to reduce the time of ur video

[sukritiguin]

great explanation sir... Please upload more and more LeetCode HARD solution...

[palakmantry]

Please can you explain time complexity?