Word Search - Leetcode 79 - Recursive Backtracking (Python)

[@GregHogg]

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

[@nikoschaitas1378]

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.

[@nikhilsastry6631]

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

[@GregHogg]

This question is part of a playlist that has all the leetcode questions I've done on there so far. I also have them in mini playlists organized by category. I hope this helps!!

[@dominikschweigl574]

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?

[@GregHogg]

Actually, no, this is not the case. It's particularly when there's exactly one spot. From the position on the last character, the board would just need literally any valid space to go to. Even if that space was marked as a hashtag or a character or whatever, it just needs an actual valid (i,j) position to move to

[@polidon1577]

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