Word Search - Backtracking - Leetcode 79 - Python

0:00 - Read the problem
1:23 - Drawing Explanation
3:06 - Coding Explanation

leetcode 79

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

[ilanaizelman]

This channel is criminally underrated.

[kokosda]

Each time I see your videos I ask myself why I overcomplicate things all the time I'm approaching a problem. Your talent is to show people a simple way of thinking!

[godspoweropara]

Hey Man...Greetings from Nigeria

Thanks for your videos, They helped me improve in DS and Algorithm. I have successfully landed a job at Google. Keep up the good work and God bless.

[DanhWasHere]

Really compact solution for this problem I don't think I've seen before! I love how you reuse depth first search as a utility algorithm for any project to make it really clear there are patterns within how some problems are solved

[SahilTechTalks]

It's crazy how simple you make seemingly insurmountable problems look, thank you.

[nehaa]

Love how you take the time to explain how to arrive at the complexity.

[tworstwots]

Instead of adding and removing from path, you can also just set the used character on the board to a dummy value (I used "."), then change it back. Works the same and saves a bit of memory and a few operations.

[weiyihuang]

Beautiful and clean code! Love how organized and simple you have made to solve the problem! Love to see more backtracking templates as it is so hard to understand....

[hithambasheir]

Works like charm 💥
A minor optimisation that I did is that I only initiate the DFS after I've checked that the current character of the board is mathcing the first char of word
if word[0] == board[i][j]: dfs
Won't make a big difference as it will be checked on the first dfs

[greyreynyn]

Thank you man, you put out quality stuff. 1 nitpick at the end, you use n to represent 2 different things in your complexity analysis; don't be afraid to use things like "w" for word length :)

[manasawalaaamir]

your coding quality is one of the best i have seen !

[Lulit]

To get turbo low runtime you have to do 2 things:

1) check if number of letters in board is enough to build the word
2) reverse word if number of first letter occurs more times than last letter of the word


We can count number of letters using Python Counter .
You can achieve it by adding the following code before running dfs:

word_dict = Counter(word)
board_dict =

if any (count > board_dict[char] for char, count in word_dict.items()):
return False

if board_dict[word[0]] > board_dict[word[-1]]:
word = word[::-1]

[samuelrobert]

Great explanation. A small optimisation can be done here to remove thte path set. Xor the char with 256 when visiting and xor it back to remove it from current path.

[akshatsamdani]

Hey I just got this question in my Deutsche bank interview and I was able to crack the question and also the FTE. Thank you so much for doing this🎉❤

[louiswoolley]

it's the best explaination i've seen so far !

[sadekjn]

Minor correction: Time complexity is actually O(m * n * 3^L), where m is the number of rows, n is the number of columns, and L is the length of the word. It's 3^L and not 4^L because we can never move backwards when searching for the next character. Also, you can save some space by just creating a temp variable, marking board[r][c] as "#" or something, and marking it back with temp after backtracking instead of using a set. Another minor optimization would also be to run backtracking in the outer function only when board[r][c] == word[0].

[AbanoubAsaad-YT]

Great Solution!
But we can optimize the space a little bit, by replacing "the set" to a "char variable" like this:
char c = board[i][j];
board[i][j] = '.';
//recurse with dfs then back track and change the board's value to previous
board[i][j] = c;

[carsenmiller]

Time complexity is actually O(N * 3^len(word)) since we don't have to go back to the direction we came from! Great solution tho

[ivandrofly]

Simple and neat :D

There is actually a wait to avoid having 4 "dfs" method you can also have some tuple with (1, 0) (0, 1), (-1, 0) (0, -1) AND iterate over them

[tranhoanglong]

A way to boost your algorithm is to make sure that all characters of the `word` is available in our `board` by checking
```
if set(word) - set([i for row in board for i in row]): return False
```
before doing the backtracking itself.

Some might argue that this takes extra time but in a problem with already backtracking-complexity (O(m.n.k^4)), an extra O(m.n) does not make any difference.
In fact this "trick" helped my solution to get ~90% best time complexity.