Word Search - Leetcode 79 - Recursive Backtracking (Python)

Please check my playlists for free DSA problem solutions:

My Favorite Courses:

Data Structures & Algorithms:

Python:

Web Dev / Full Stack:

Cloud Development:

Game Development:

SQL & Data Science:

Machine Learning & AI:

[GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[nikoschaitas]

Seems like they added another test case that will prevent you from submitting successfully.

board =
[["a"]]

word =
"ab"

In C++, you could do the following check before m==1 && n==1:
if (word.size() > m*n)
return false;

At least it worked for me, with a not so pretty runtime of 576 ms.

Again, thanks Greg! Probably wouldn't have understood the problem without this video!

[MaHyxa]

Hey Greg, thanks for the lesson. Just want to let you know that on your GitHub java solution you dont need this statement:

if (m == 1 && n == 1) {
return board[0][0] == word.charAt(0);
}

because it's failing test with a single letter in a board and always returning true without checking size of the word.

And also you've declared a variable W, but never used it in code.

[nikhilsastry]

Hey greg ... Can you make a video or make a pdf of something that consists all strings based ir other all category algorithms ... I want particularly for string like kmp ..m can you put all the algos at one place from easy to hard

[dominikschweigl]

Doesnt that mean your solution doesnt work whenever the word is taking up the whole grid? Like in the example for 1x1 there is nowhere to go to and it would return false, right?

[polidon]

would it be possible to store dead end sequences with the positions so that if you have a second attempt reach there in the same way, it would cancel early instead of tracing the whole word? I think that would help reduce the time complexity but I'm not sure how much that would impact the space complexity if it's even viable to do so

[thatnolan]

Any reason to use pos in backtrack() instead of i, j? You change it back to i, j in the first time anyways. The efficiency goes up quite a bit when changing pos to i, j