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!
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
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.
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
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].
I think you can even make it more efficient than that, and that the exponential is a huge upper bound. Because you have a visited set, you can never visit any element more than once. Worst case scenario therefore is that the DFS visits every cell (which probably wouldn't happen multiple times), which is m*n. So I think it is O(m^2n^2). Happy to be corrected
@@charlietian4023 That's not right. Say you start at (0,0). You could end up at (1,1) via (0,1) or via (1,0). Already, we can see that (1,1) got visited more than once from a given start position.
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 = Counter(itertools.chain.from_iterable(board))
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]
@A if last letter occurs only once then search will trigger only once. If first letter occurs for example 10 times then it will trigger 10 times (so it will make 10x higher time complexity).
@@pl5778 For example, if we are looking for word "hi", in an array of [h,h,h,i,], if you choose the match the first char "h" to start the dfs, it will trigger 3 times. However, if you choose the last char "i" to start dfs, it would only trigger once.
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.
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....
for anyone who get a problem with time Limit Exeeded. Try instead of a set so save tmp = board[r][c] and then set it to zero or so where you would add (r,c) to set. And when you remove (r,c) set tmp to board[r][c] again.
@@abhayk3339 tmp = board[r][c] board[r][c] = '#' #find res board[r][c] = tmp in this way instead of using set to save the coordinates, you are marking the visited character by #
Can you please explain how this is helpful for time? Because as far as my understanding goes, isn't adding and removing from set also constant time operations.
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.
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 :)
To prevent TLE, I combined other's code from leetcode discussion, 1) reverse word if freqency of first word is larger than the last of word, 2) instead of using set to storage visited coordinates, modify the char on board directly, 3) only start the search when the first char match the first char of the word class Solution(object): def exist(self, board, word): """ :type board: List[List[str]] :type word: str :rtype: bool """ R, C = len(board), len(board[0]) if word.count(word[0]) > word.count(word[-1]): word = word[::-1] def dfs(r, c, ci): if ci == len(word): return True if r < 0 or c < 0 or r >= R or c >= C: return False if board[r][c] != word[ci]: return False curr = board[r][c] board[r][c] = "#" a1 = dfs(r + 1, c, ci + 1) b1 = dfs(r - 1, c, ci + 1) c1 = dfs(r, c + 1, ci + 1) d1 = dfs(r, c - 1, ci + 1) board[r][c] = curr return a1 or b1 or c1 or d1
for r in range(R): for c in range(C): if board[r][c] == word[0] and dfs(r, c, 0): return True
I feel like reversing doesn't work, as efficently. Maybe for some cases like "aaaaaaaaaaaab" but the issue comes in a word like "aaaaaaaabaaaaaaaa", for back to front it's the same essentially a plaindrome. And also you have to check the frequency of chars from back to front in order to execute reversal. Rather take a preliminary test, where check if all the unique characters of the word does appear in board or not. If not return false
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;
You actually don't even need to store the letter in a new variable, you can just: ... board[r][c] = '.' ... # recurse then backtrack board[r][c] = word[i] ...
Something I did to improve the performance a bit is checking if the last character is repeated less than the first character, if so just reverse the word and search, you will be searching from less starting points which means less search overall
/// Optimization if the count of the last char, is less than the count of first char this means if you start from the end /// you get less starting points => less search if (word[0] != word[^1]) { var fC = word.Where(c => c == word[0]).Count(); var lC = word.Where(c => c == word[^1]).Count(); if (lC < fC) word = new string(word.Reverse().ToArray()); }
Thanks for your great channel, it is handy for me. I just wanted to let you know that a more efficient solution for solving this problem is to use backtracking with DFS without using a Set. Instead, mark the visited nodes directly on the board by temporarily changing their values. After DFS, revert the board to its original state. /** * @param {character[][]} board * @param {string} word * @return {boolean} */ var exist = function (board, word) { let rows = board.length; let cols = board[0].length; function dfs(r, c, i) { if (i === word.length) return true; if (r < 0 || c < 0 || r >= rows || c >= cols || board[r][c] !== word[i]) return false; let temp = board[r][c]; board[r][c] = '#'; // Mark as visited let res = ( dfs(r - 1, c, i + 1) || // Up dfs(r + 1, c, i + 1) || // Down dfs(r, c - 1, i + 1) || // Left dfs(r, c + 1, i + 1) // Right ); board[r][c] = temp; return res; } for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { if (dfs(r, c, 0)) return true; } } return false; };
One thing you can do to reduce the Time Complexity here is to modify the board itself that when transversing from a position we mark that position with a special character and then restore after we are done. ``` board[r][c] = '*' ... board[r][c] = word[index] ```
A great solution... A suggestion if we only call the function inside the loop whenever board[i][j] == word[0], rather than every element of the board, that will save us a lot of time.
Saying that it will save a lot of time is a little bit of an exaggeration. At most it will save a few processor cycles from invoking another function that will immediately return.
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
I got a question very close to this during an OA, and I was so worried about efficiency since my solution was... Not. Glad to see that there isn't really a perfectly efficient way to solve this :)
Thank you for always including the time complexity calculation in every problem. One extra suggestion is also try to include space complexity. ♥your stuff man
A slight improvement to the problem can be done as follows. While making initial dfs calls inside the nested for loops, we can only make those calls if word[0] equals the board[r][c] value. This would reduce the unnecessary calls made for each board position
Another improvement I found out from Chat GPT is that instead of using a set to save all visited cells, we can temporarily assign a special character to the cell before the loop and then tmp, A[r][c] = A[r][c], '#' for dx, dy in directions: if dfs(r + dx, c + dy, k + 1): return True A[r][c] = tmp
hey man, Thanks for all the help with these videos! I'm a software engineer at a fairly large tech company but haven't had a lot of time to work on code at all and forgot a lot of my knowledge from college. Hoping to apply to FAANG companies soon and these videos really have been pulling me along! I haven't found anyone else who makes videos as well as you. question, could you make a video involving Tries? I haven't seen any on your channel and think it would be great. keep up the good work man :)
Thanks for this solution. I also implemented it using a HashSet (C#) but the runtime was bad. Then I switched to modifying the traversed cell and it was 5 times faster.
I don't think LC is accepting this answer anymore, I'm getting a TLE with the same approach (but if I submit multiple times sometimes it will accept it)
now you need to add a "pre-check" before your code to change it from a TLE solution to a solution beats 95% submissions.(directly return false if you find the board can not even provide all letters): charCount = defaultdict(lambda:0) for i in range(len(board)): for j in range(len(board[0])): charCount[board[i][j]] += 1 for ch in word: charCount[ch] -= 1 if charCount[ch]
@@jiachuandeng1795 Nice! You missed to check if the character from the word is even present in the map: for c in word: if c not in count: return False count[c] -= 1 if count[c] < 0: return False
@@K_CO_ManuSingh Basically, checking is it even possible for the word to exist in the table, by making a hashmap where the keys are all the characters from the table, and the values are the number of occurrences for each of those characters. That's the first for-loop. As for the second for-loop, suppose now that: 1. Your word has a character that is not event present in that hashmap, i.e. the table doesn't contain that character at all. 2. Your word has multiple occurrences of a character, but the table actually doesn't have that many occurrences of that same particular character. In either of those cases, does it make sense to go on? Edit: Oops, didn't see the great reply from Brandon.
For the time complexity analysis, I think you can even make it more efficient than that, and that the exponential is a huge upper bound. Because you have a visited set, you can never visit any element more than once. Worst case scenario therefore is that the DFS visits every cell (which probably wouldn't happen multiple times), which is m*n. So I think it is O(m^2n^2). Happy to be corrected
I just realized this could be wrong because of the backtracking nature of the problem. It is quite possible that a dfs starting at a cell could revisit some nodes again and again but via a different path
Nice solution! However, I think the dfs would be more clear by the following: bool dfs (int i, int j, int offset, string& str) { if (offset == str.size()) return true; if (i < 0 || j < 0 || i >= row || j >= col || matrix[i][j] != str[offset]) return false; char tmp = matrix[i][j]; matrix[i][j] = '*'; bool res; res = dfs(i + 1, j, offset + 1, str) || dfs(i - 1, j, offset + 1, str) || dfs(i, j - 1, offset + 1, str) || dfs(i, j + 1, offset + 1, str); if (!res) matrix[i][j] = tmp; return res; }; In this question, the elements in the set are not important, which means we don't need to store the correct ones of the result. But it could store satisfying elements actually. If the dfs result of an element is true, which means we need it to compose "word", we mark it as visited. If not, this element is free and we recover to its original value. Am I right?
I found my solution with O(n!) complexity (at least I think so), but haven't implemented it. 1) get all elements with their indexes (x, y) if they exist in word and store them in the array 2) then find a combination of indexes that can go according to our condition So we don't have to run through all elements when we can just go through correct elements
I feel we can do 2 optimizations 1. if we use a temp variable to change the value of a cell instead of hash set we can reduce the operations of insert and remove 2. Instead of checking all directions in "res", if we use if-else cases then if one direction is True then we can return True and go to next step. That way we can reduce some iterations
The solution in the video already does what you are talking about in #2. That's because in Python (and most languages), operators like "and" and "or" are short-circuiting, meaning they only evaluate as many arguments as needed to get an answer. If you do "x or y," y will only be evaluated if x is false. If you do "x and y," y will only be evaluated if x is true. Etc.
You can also return False if there is a character in the word which is not present in the entire board before calling the dfs. This would take up extra memory, but that can be a constant given the constraints of this problem i.e. board and word consists of only lowercase and uppercase English letters. This could address some of the worst case complexities. And, for larger board sizes, we can have a lookup dictionary / list of sorts containing the indices for the first character. This way, we don't have to go through the entire board. Great solution however!
This comment is 10 months old. Nevertheless, I wanted to ask you about tracking the first letter of the word for "larger board sizes, we can have a lookup dictionary..." to avoid going "...through the entire board." But, I think, to populate such a lookup dictionary of first letter of word found in board, we have to go through the entire board to find them? Or am I missing something?
That line needs to be there to clean up the set path because after the 4 other calls to dfs (we're done with the search starting from (r,c)) we should be allowed to visit (r,c) again if we run dfs from another cell (which we do, within the next iteration called from the nested for loops).
thank you for the amazing content and explanation; could you please explain why the (r, c) combinations needs to be removed from path after the adjacent cells have been visited; I have little understanding that it needs to be removed so that the next path/word combination can utilize it again if needed; but I am not sure if that is the correct reason.
My understanding is that for each square we need to do DFS, so after each complete DFS we need to empty the set. The return is at the end of the function after the DFS is complete.
@@charlesyam804 If you meant that we need to start from an empty set for every iteration in the for loop, I think it is not the main reason for the removal although the set indeed needs to be empty for every iteration. To check this, you can simply empty the set manually in the for a loop every iteration, and then see your code fails at LeetCode submission. That being said, the main reason could be the following: Let's assume that your first dfs, out of the four dfs calls connected with "or", returns False. Although it returns False, it adds r+1, c to the path if you don't have ""path.remove((r,c,))". Then, if the second dfs out of the four is supposed to be the right path while the path after a few recursion is getting later to the same r+1,c position in the first dfs call, the position is already in the path thus returning False. This is not what we want.
Enable Backtracking: After exploring all potential paths from a particular cell, we need to backtrack to explore other possibilities from previous cells. Removing the cell from the visited set allows it to be considered again in a different path. This is essential because the same cell might be part of multiple different paths leading to the word.
Great work. Very pythonic style! Do you think there's any chance this one can be solved using an iterative stack solution? (I mean, with the recursive way we only have to change back the status of one point in one call, but with iterative the whole path might need to be reclaimed) I tried hard on this idea because it came to my mind first, but couldn't figure out how to manage the stack and undo the changes correctly.
I like the way you explain the solution. Can you also provide an iterative solution using stack? Most interviewers don't prefer recursion since real world hardly uses a recursion solutions.
Have you found the answer? Stuck with the same question right now... Obviously, LC does not accept the solution without this line. But I don't get why it plays any role here.
Enable Backtracking: After exploring all potential paths from a particular cell, we need to backtrack to explore other possibilities from previous cells. Removing the cell from the visited set allows it to be considered again in a different path. This is essential because the same cell might be part of multiple different paths leading to the word.
I was searching the youtube solution of leetcode 1849 (the recent contest prob 2) and youtube recommended me NeetCode channel. I was amazed of the explanation and I'm checking into all the other videos of him. Just one word. Dope :) Love you brother. :)
Super nitpicking here but it's actual O(n * 3^L) because you one of the tiles will always be something you've already visited. So your next letter options would always be 3. So that's the 3^L where L is the length of the word. I just want to sound smart for once. I actually can't figure this problem out without your video haha.
BTW adding this check before Line #25 will help in increasing the performance? As it will reduce the number of calls. if board[r][c] != word[0]: continue
Thank you for the detailed explanation! I check on your website, but I don't quite understand why reversing the word if the frequency of the first character is larger than the frequency of the last character? It kind of seems "out of nowhere" even thought it does work.
I am rethinking the complexity of the dfs. You mentioned it is 4^(length-of-word). But dfs is normally O(m*n) using the visited boolean array (in this case you are using set to track that). So, should not the dfs runtime for this problem should be O(m*n) ? However, 4^(length of word)
My understanding is that for each square we need to do DFS, so after each complete DFS we need to empty the set. The return is at the end of the function after the DFS is complete.
@@charlesyam804 If you meant that we need to start from an empty set for every iteration in the for loop, I think it is not the main reason for the removal although the set indeed needs to be empty for every iteration. To check this, you can simply empty the set manually in the for a loop every iteration, and then see your code fails at LeetCode submission. That being said, the main reason could be the following: Let's assume that your first dfs, out of the four dfs calls connected with "or", returns False. Although it returns False, it adds r+1, c to the path if you don't have ""path.remove((r,c,))". Then, if the second dfs out of the four is supposed to be the right path while the path after a few recursion is getting later to the same r+1,c position in the first dfs call, the position is already in the path thus returning False. This is not what we want.
Amazing explanation as always, just one small doubt- why are we removing (r,c) from path every time, like we are obviously checking the path in the if condition right? so what's the point of removing it later?
hey man, your videos are very helpful to learn DS for new or advance guy who want to learn. Please create the playlist on greedy aproach also. Thanks❤❤❤❤❤❤❤❤❤❤❤❤❤❤
Is it possible to solve this problem using a prefix tree (Trie)? I thought the most intuitive thing to do was to solve it using a prefix tree. Thank you for your time and I hope a favourable reply 🙏 Best regards.
path corresponds to the cells that have already been visited as part of the call to dfs() . Note dfs() is being called for each character on the board (See the nested loops at the end). We remove the tuple from the path to prevent side effects. Another option would be to clear path before calling dfs(r.c.0) . But this would add to the space complexity.
Can everyone aspire to get good at this stuff? or is it something that you either have it or you don't? I sometimes think that I can solve this problems but in no way I could finish them before the 30 minutes you are given during the interview. I really want to get better at these
Is the space complexity of this solution also O(4^k) where k == len(word)? My reasoning: since each dfs call will be an element on the call-stack it would take up memory each time.
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
Getting TLE error, what to modify?
This channel is criminally underrated.
let it remain so
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!
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
agree, this has been really helpful for learning problems! he reuses a lot of patterns/algos when possible
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.
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
It's crazy how simple you make seemingly insurmountable problems look, thank you.
ok
Love how you take the time to explain how to arrive at the complexity.
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].
I think you can even make it more efficient than that, and that the exponential is a huge upper bound. Because you have a visited set, you can never visit any element more than once. Worst case scenario therefore is that the DFS visits every cell (which probably wouldn't happen multiple times), which is m*n. So I think it is O(m^2n^2). Happy to be corrected
This is incorrect. You might visit the same cell in a single DFS multiple times if the first path through that cell does not work.@@charlietian4023
@@charlietian4023 That's not right. Say you start at (0,0). You could end up at (1,1) via (0,1) or via (1,0). Already, we can see that (1,1) got visited more than once from a given start position.
@@marredcheese yeah I think I misunderstood his visited checking and made the correction in another comment thread
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 = Counter(itertools.chain.from_iterable(board))
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]
This saved my day
Wow, top tier comment!
@A if last letter occurs only once then search will trigger only once. If first letter occurs for example 10 times then it will trigger 10 times (so it will make 10x higher time complexity).
@@Lulit999 could you help expand the explanation more. What exactly will be called 10 times? much appreciated
@@pl5778 For example, if we are looking for word "hi", in an array of [h,h,h,i,], if you choose the match the first char "h" to start the dfs, it will trigger 3 times. However, if you choose the last char "i" to start dfs, it would only trigger once.
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.
nice little optimization, thanks
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....
for anyone who get a problem with time Limit Exeeded. Try instead of a set so save tmp = board[r][c] and then set it to zero or so where you would add (r,c) to set. And when you remove (r,c) set tmp to board[r][c] again.
I am facing the Time Limit exceeded problem. I am not able to understand what are you trying to say? can u explain a bit more pls
@@abhayk3339
tmp = board[r][c]
board[r][c] = '#'
#find res
board[r][c] = tmp
in this way instead of using set to save the coordinates, you are marking the visited character by #
Can you please explain how this is helpful for time?
Because as far as my understanding goes, isn't adding and removing from set also constant time operations.
@@sanskartiwari2496 but the worst complexity for looking into a set is O(n) may be that is the reason for TLE
@@abhayk3339
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
ROWS, COLS = len(board), len(board[0])
def dfs(r,c,i):
if i == len(word):
return True
if (r = COLS or word[i]!= board[r][c]):
return False
temp = board[r][c]
board[r][c] = "#"
res = (dfs(r+1, c, i+1) or dfs(r-1, c, i+1) or dfs(r, c+1, i+1) or dfs(r, c-1, i+1))
board[r][c] = temp
return res
for r in range(ROWS):
for c in range(COLS):
if board[r][c] == word[0]:
if dfs(r,c,0):
return True
return False
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
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.
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 :)
That's a good point! Will keep that in mind for future videos
your coding quality is one of the best i have seen !
To prevent TLE, I combined other's code from leetcode discussion,
1) reverse word if freqency of first word is larger than the last of word,
2) instead of using set to storage visited coordinates, modify the char on board directly,
3) only start the search when the first char match the first char of the word
class Solution(object):
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
R, C = len(board), len(board[0])
if word.count(word[0]) > word.count(word[-1]):
word = word[::-1]
def dfs(r, c, ci):
if ci == len(word):
return True
if r < 0 or c < 0 or r >= R or c >= C:
return False
if board[r][c] != word[ci]:
return False
curr = board[r][c]
board[r][c] = "#"
a1 = dfs(r + 1, c, ci + 1)
b1 = dfs(r - 1, c, ci + 1)
c1 = dfs(r, c + 1, ci + 1)
d1 = dfs(r, c - 1, ci + 1)
board[r][c] = curr
return a1 or b1 or c1 or d1
for r in range(R):
for c in range(C):
if board[r][c] == word[0] and dfs(r, c, 0):
return True
return False
Why not check if (dfs(r + 1, c, ci + 1)) then return true instantly? If I understand right, in this case we won't compute the remaining directions.
Reversing the word worked! thanks!
Really elegant solution!
I feel like reversing doesn't work, as efficently. Maybe for some cases like "aaaaaaaaaaaab" but the issue comes in a word like "aaaaaaaabaaaaaaaa", for back to front it's the same essentially a plaindrome. And also you have to check the frequency of chars from back to front in order to execute reversal.
Rather take a preliminary test, where check if all the unique characters of the word does appear in board or not. If not return false
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;
osm! i was thinking the same
💜
You actually don't even need to store the letter in a new variable, you can just:
...
board[r][c] = '.'
... # recurse then backtrack
board[r][c] = word[i]
...
@@thomasgeorge5261 Nice!
Something I did to improve the performance a bit is checking if the last character is repeated less than the first character, if so just reverse the word and search, you will be searching from less starting points which means less search overall
/// Optimization if the count of the last char, is less than the count of first char this means if you start from the end
/// you get less starting points => less search
if (word[0] != word[^1])
{
var fC = word.Where(c => c == word[0]).Count();
var lC = word.Where(c => c == word[^1]).Count();
if (lC < fC)
word = new string(word.Reverse().ToArray());
}
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🎉❤
Space complexity can be reduced by marking off (r,c) with a # or a * on the board itself rather than using sets. Thanks for the great video.
but how do you get the lost information back? once you mark it off with #? can anyone elaborate? appreciate it.
@@kamaleshs5324 you can add a check if the current word is '#' then it means we have visited it and hence return a false in the base case
it's the best explaination i've seen so far !
Instead of running dfs for each cell, just run it for the cells that contain the first letter of the word and a bit of time can be saved.
I believe he does that in the second if statement, specifically word[i] != board[r][c]
Thanks for your great channel, it is handy for me. I just wanted to let you know that a more efficient solution for solving this problem is to use backtracking with DFS without using a Set. Instead, mark the visited nodes directly on the board by temporarily changing their values. After DFS, revert the board to its original state.
/**
* @param {character[][]} board
* @param {string} word
* @return {boolean}
*/
var exist = function (board, word) {
let rows = board.length;
let cols = board[0].length;
function dfs(r, c, i) {
if (i === word.length) return true;
if (r < 0 || c < 0 || r >= rows || c >= cols || board[r][c] !== word[i]) return false;
let temp = board[r][c];
board[r][c] = '#'; // Mark as visited
let res = (
dfs(r - 1, c, i + 1) || // Up
dfs(r + 1, c, i + 1) || // Down
dfs(r, c - 1, i + 1) || // Left
dfs(r, c + 1, i + 1) // Right
);
board[r][c] = temp;
return res;
}
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (dfs(r, c, 0)) return true;
}
}
return false;
};
One thing you can do to reduce the Time Complexity here is to modify the board itself that when transversing from a position we mark that position with a special character and then restore after we are done.
```
board[r][c] = '*'
...
board[r][c] = word[index]
```
A great solution... A suggestion if we only call the function inside the loop whenever board[i][j] == word[0], rather than every element of the board, that will save us a lot of time.
Saying that it will save a lot of time is a little bit of an exaggeration. At most it will save a few processor cycles from invoking another function that will immediately return.
it won't save much time because you're checking that top condition inside dfs anyway
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
Man, you are the best in explanations.
I Watch your almost every day before bed :)
I got a question very close to this during an OA, and I was so worried about efficiency since my solution was... Not. Glad to see that there isn't really a perfectly efficient way to solve this :)
Thank you for always including the time complexity calculation in every problem. One extra suggestion is also try to include space complexity. ♥your stuff man
A slight improvement to the problem can be done as follows.
While making initial dfs calls inside the nested for loops, we can only make those calls if word[0] equals the board[r][c] value. This would reduce the unnecessary calls made for each board position
it decreases my runtime to 32%, thanks (I know leetcode's runtime is kinda hoax tho lol)
Yes the leetcode runtime shows bizarre results at time but logically this should reduce the runtime slightly
Another improvement I found out from Chat GPT is that instead of using a set to save all visited cells, we can temporarily assign a special character to the cell before the loop and then
tmp, A[r][c] = A[r][c], '#'
for dx, dy in directions:
if dfs(r + dx, c + dy, k + 1):
return True
A[r][c] = tmp
this works, but usually interviewers wouldnt like it if you modify the input.
Thanks for the great explanation.
Btw, this solution on LeetCode gets Time Limit Exceeded - wondering if there's a faster way?
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
ROWS, COLS = len(board), len(board[0])
def dfs(r, c, i):
if i == len(word):
return True
if (
min(r, c) < 0
or r >= ROWS
or c >= COLS
or word[i] != board[r][c]
):
return False
temp = board[r][c]
board[r][c] = "#"
res = (
dfs(r + 1, c, i + 1)
or dfs(r - 1, c, i + 1)
or dfs(r, c + 1, i + 1)
or dfs(r, c - 1, i + 1)
)
board[r][c] = temp
return res
for r in range(ROWS):
for c in range(COLS):
if dfs(r, c, 0):
return True
return False
just a few changes to the code.
you can add this pruning snippet before we start dfs:
s = ''"
for row in board:
s=s+"''.join(row)
for i in word:
if i not in s:
return False
Thanks to watching a lot of your videos and working through the Roadmap, I was able to get this optimal solution on my own!
hey man, Thanks for all the help with these videos!
I'm a software engineer at a fairly large tech company but haven't had a lot of time to work on code at all and forgot a lot of my knowledge from college. Hoping to apply to FAANG companies soon and these videos really have been pulling me along! I haven't found anyone else who makes videos as well as you.
question, could you make a video involving Tries? I haven't seen any on your channel and think it would be great. keep up the good work man :)
Thanks Matthew for the kind words! Yeah, I plan on doing some Trie questions soon.
Same here bro
hey what kind of projects have you made before applying to faang
@@kaushik.aryan04 no one looks at projects once you have work ex lol
@@gagandeepgopalaiah6144 I am in 2nd year college I only have 3 months internship experience
when i solved it my time time complexity was just 13.91 %.... yours was way faster...Awesome Solution!!!
How would you approach the follow-up question:
"Could you use search pruning to make your solution faster with a larger board?"
Thanks for this solution. I also implemented it using a HashSet (C#) but the runtime was bad. Then I switched to modifying the traversed cell and it was 5 times faster.
Great work. Crystal clear explanation. Can you please post templates like backtracking which can be reused for other problem
I don't think LC is accepting this answer anymore, I'm getting a TLE with the same approach (but if I submit multiple times sometimes it will accept it)
now you need to add a "pre-check" before your code to change it from a TLE solution to a solution beats 95% submissions.(directly return false if you find the board can not even provide all letters):
charCount = defaultdict(lambda:0)
for i in range(len(board)):
for j in range(len(board[0])):
charCount[board[i][j]] += 1
for ch in word:
charCount[ch] -= 1
if charCount[ch]
@@jiachuandeng1795 could you explain what you are trying to do here?
@@jiachuandeng1795 This worked for me. The code + Neetcode's solution beats 96% of other solutions in runtime
@@jiachuandeng1795 Nice! You missed to check if the character from the word is even present in the map:
for c in word:
if c not in count:
return False
count[c] -= 1
if count[c] < 0:
return False
@@K_CO_ManuSingh Basically, checking is it even possible for the word to exist in the table, by making a hashmap where the keys are all the characters from the table, and the values are the number of occurrences for each of those characters. That's the first for-loop.
As for the second for-loop, suppose now that:
1. Your word has a character that is not event present in that hashmap, i.e. the table doesn't contain that character at all.
2. Your word has multiple occurrences of a character, but the table actually doesn't have that many occurrences of that same particular character.
In either of those cases, does it make sense to go on?
Edit: Oops, didn't see the great reply from Brandon.
For the time complexity analysis,
I think you can even make it more efficient than that, and that the exponential is a huge upper bound. Because you have a visited set, you can never visit any element more than once. Worst case scenario therefore is that the DFS visits every cell (which probably wouldn't happen multiple times), which is m*n. So I think it is O(m^2n^2). Happy to be corrected
I just realized this could be wrong because of the backtracking nature of the problem. It is quite possible that a dfs starting at a cell could revisit some nodes again and again but via a different path
However, I suggest renaming your variable for len(word) to be w, as n is already the number of columns
Nice solution!
However, I think the dfs would be more clear by the following:
bool dfs (int i, int j, int offset, string& str) {
if (offset == str.size()) return true;
if (i < 0 || j < 0 || i >= row || j >= col || matrix[i][j] != str[offset]) return false;
char tmp = matrix[i][j];
matrix[i][j] = '*';
bool res;
res = dfs(i + 1, j, offset + 1, str) ||
dfs(i - 1, j, offset + 1, str) ||
dfs(i, j - 1, offset + 1, str) ||
dfs(i, j + 1, offset + 1, str);
if (!res) matrix[i][j] = tmp;
return res;
};
In this question, the elements in the set are not important, which means we don't need to store the correct ones of the result. But it could store satisfying elements actually. If the dfs result of an element is true, which means we need it to compose "word", we mark it as visited. If not, this element is free and we recover to its original value. Am I right?
I found my solution with O(n!) complexity (at least I think so), but haven't implemented it.
1) get all elements with their indexes (x, y) if they exist in word and store them in the array
2) then find a combination of indexes that can go according to our condition
So we don't have to run through all elements when we can just go through correct elements
You don't need to create excess space with the set. You can just edit the board itself to mark visited positions.
you can cache and mark off the current selection with a special character, then case the value back after backtracking, thus reduce the memory
I feel we can do 2 optimizations
1. if we use a temp variable to change the value of a cell instead of hash set we can reduce the operations of insert and remove
2. Instead of checking all directions in "res", if we use if-else cases then if one direction is True then we can return True and go to next step. That way we can reduce some iterations
The solution in the video already does what you are talking about in #2. That's because in Python (and most languages), operators like "and" and "or" are short-circuiting, meaning they only evaluate as many arguments as needed to get an answer. If you do "x or y," y will only be evaluated if x is false. If you do "x and y," y will only be evaluated if x is true. Etc.
@@marredcheese I thought it will check all directions. It is same for any() and all() as well right
@@midhileshmomidi3120 yeah, those short-circuit too
OR statements already Short circuit
Great explanation. Also I wrote in JS where the first if statement inside dfs() had to be written after 2nd if in line number 9.
You can also return False if there is a character in the word which is not present in the entire board before calling the dfs. This would take up extra memory, but that can be a constant given the constraints of this problem i.e. board and word consists of only lowercase and uppercase English letters. This could address some of the worst case complexities. And, for larger board sizes, we can have a lookup dictionary / list of sorts containing the indices for the first character. This way, we don't have to go through the entire board.
Great solution however!
This comment is 10 months old. Nevertheless, I wanted to ask you about tracking the first letter of the word for "larger board sizes, we can have a lookup dictionary..." to avoid going "...through the entire board." But, I think, to populate such a lookup dictionary of first letter of word found in board, we have to go through the entire board to find them? Or am I missing something?
Nice explanation.. :)
But I didn't get why you removed the (r, c) from the path at the end
That line needs to be there to clean up the set path because after the 4 other calls to dfs (we're done with the search starting from (r,c)) we should be allowed to visit (r,c) again if we run dfs from another cell (which we do, within the next iteration called from the nested for loops).
thank you for the amazing content and explanation; could you please explain why the (r, c) combinations needs to be removed from path after the adjacent cells have been visited; I have little understanding that it needs to be removed so that the next path/word combination can utilize it again if needed; but I am not sure if that is the correct reason.
My understanding is that for each square we need to do DFS, so after each complete DFS we need to empty the set. The return is at the end of the function after the DFS is complete.
@@charlesyam804 If you meant that we need to start from an empty set for every iteration in the for loop, I think it is not the main reason for the removal although the set indeed needs to be empty for every iteration. To check this, you can simply empty the set manually in the for a loop every iteration, and then see your code fails at LeetCode submission. That being said, the main reason could be the following: Let's assume that your first dfs, out of the four dfs calls connected with "or", returns False. Although it returns False, it adds r+1, c to the path if you don't have ""path.remove((r,c,))". Then, if the second dfs out of the four is supposed to be the right path while the path after a few recursion is getting later to the same r+1,c position in the first dfs call, the position is already in the path thus returning False. This is not what we want.
@@jaejincho9921, no it doesnt add (r+1, c) because the return false is written before the .add. so it doesnt reach there
Enable Backtracking: After exploring all potential paths from a particular cell, we need to backtrack to explore other possibilities from previous cells. Removing the cell from the visited set allows it to be considered again in a different path. This is essential because the same cell might be part of multiple different paths leading to the word.
took me awhile to understand why path.add, path.remove is needed. basically this condition make sure there is no cross over in the path.
Great work. Very pythonic style! Do you think there's any chance this one can be solved using an iterative stack solution? (I mean, with the recursive way we only have to change back the status of one point in one call, but with iterative the whole path might need to be reclaimed) I tried hard on this idea because it came to my mind first, but couldn't figure out how to manage the stack and undo the changes correctly.
I like the way you explain the solution. Can you also provide an iterative solution using stack? Most interviewers don't prefer recursion since real world hardly uses a recursion solutions.
in the real world you call APIs and DBs.. not solve leetcode problems.
Can anyone explain why we need to remove (r,c) from the path before returning res? thanks
Have you found the answer?
Stuck with the same question right now...
Obviously, LC does not accept the solution without this line. But I don't get why it plays any role here.
Enable Backtracking: After exploring all potential paths from a particular cell, we need to backtrack to explore other possibilities from previous cells. Removing the cell from the visited set allows it to be considered again in a different path. This is essential because the same cell might be part of multiple different paths leading to the word.
So that when you traverse a different path, you don’t block yourself from visiting that letter
It's funny hearing you lean back/get off from your chair at the end lol
I was searching the youtube solution of leetcode 1849 (the recent contest prob 2) and youtube recommended me NeetCode channel. I was amazed of the explanation and I'm checking into all the other videos of him. Just one word. Dope :) Love you brother. :)
What do we need to learn before starting to learn about dynamic programming?
Super nitpicking here but it's actual O(n * 3^L) because you one of the tiles will always be something you've already visited. So your next letter options would always be 3. So that's the 3^L where L is the length of the word. I just want to sound smart for once. I actually can't figure this problem out without your video haha.
This template i often use
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
def valid(i,j, wIdx):
if i>=0 and j>=0 and i
Great explaination as always!🙏 Thanks
We can add a condition in the for loop where if the first character of the word matches board[i][j] only than go for a dfs
that is the best video of leetcode 79 so far
Thanks for this beautiful code..yes, its not very efficient...is ther another way to make it more efficient?
I get to learn from the greatest teacher.
Good Solution and Good Explaination also
Very good solution
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
m, n = len(board), len(board[0])
word_len = len(word)
def dfs(i, j, index):
if index==word_len: return True
if i
this solution gives TLE now
I got TLE using your solution, but I tried adding 'if board[i][j] == word[0]:' before doing dfs. This worked for me, hope it can help someone else
literally spend an hour debugging this. Wish I saw this earlier.
@@gabrielraphaelgarciamontoy1269 glad it's helpful, happy coding!
Thanks this really helped
Your explanation is very clear. Thanks!
BTW adding this check before Line #25 will help in increasing the performance? As it will reduce the number of calls.
if board[r][c] != word[0]:
continue
This avoided the TLE
i m not convinced that we need to remove the last node from path.. but it does give the correct answer.
שאלות מופתעת ❤
Thank you for the detailed explanation! I check on your website, but I don't quite understand why reversing the word if the frequency of the first character is larger than the frequency of the last character? It kind of seems "out of nowhere" even thought it does work.
I am rethinking the complexity of the dfs. You mentioned it is 4^(length-of-word). But dfs is normally O(m*n) using the visited boolean array (in this case you are using set to track that). So, should not the dfs runtime for this problem should be O(m*n) ? However, 4^(length of word)
Why do you remove the tuple from path in line 20? I thought the point was to check elements that were not visited.
My understanding is that for each square we need to do DFS, so after each complete DFS we need to empty the set. The return is at the end of the function after the DFS is complete.
@@charlesyam804 If you meant that we need to start from an empty set for every iteration in the for loop, I think it is not the main reason for the removal although the set indeed needs to be empty for every iteration. To check this, you can simply empty the set manually in the for a loop every iteration, and then see your code fails at LeetCode submission. That being said, the main reason could be the following: Let's assume that your first dfs, out of the four dfs calls connected with "or", returns False. Although it returns False, it adds r+1, c to the path if you don't have ""path.remove((r,c,))". Then, if the second dfs out of the four is supposed to be the right path while the path after a few recursion is getting later to the same r+1,c position in the first dfs call, the position is already in the path thus returning False. This is not what we want.
Happy to see you back bro
Why i == len(word) not i == len(word) - 1? Aren't we starting at 0 index
Amazing explanation as always, just one small doubt-
why are we removing (r,c) from path every time, like we are obviously checking the path in the if condition right? so what's the point of removing it later?
as we are moving out from that stack or recursive call we have to undo its operations, pepcoding has visually explained this.
hey man, your videos are very helpful to learn DS for new or advance guy who want to learn. Please create the playlist on greedy aproach also. Thanks❤❤❤❤❤❤❤❤❤❤❤❤❤❤
Question for the Java solution. Is "board[i][j] += 100" supposed to be a marker for the already visited character?
i am a beginner in python i wanted to ask that when ever we are searching the element or letter can't we just use the dictionary i am just asking 😅
Is it possible to solve this problem using a prefix tree (Trie)?
I thought the most intuitive thing to do was to solve it using a prefix tree.
Thank you for your time and I hope a favourable reply 🙏
Best regards.
Could you plz elaborate as to why are we removing the path before returning. Couldn't get you.
path corresponds to the cells that have already been visited as part of the call to dfs() . Note dfs() is being called for each character on the board (See the nested loops at the end). We remove the tuple from the path to prevent side effects.
Another option would be to clear path before calling dfs(r.c.0) . But this would add to the space complexity.
@@danielladsouza8045 What would the space complexity be for NeetCode's solution?
Can everyone aspire to get good at this stuff? or is it something that you either have it or you don't? I sometimes think that I can solve this problems but in no way I could finish them before the 30 minutes you are given during the interview. I really want to get better at these
Thank you... But is there a better solution?
Is the space complexity of this solution also O(4^k) where k == len(word)?
My reasoning: since each dfs call will be an element on the call-stack it would take up memory each time.
No, it should be O(k), the size of the call stack is at most the height of the recursion tree
Loved it man. Thank you so much
Hi, Regarding the solution provided for Time limit Exceeded in the website. How did reversing the word helped in preventing TLE?
best content ever, very good
I keep getting a time limit error using this solution for the all 'A' case on Leetcode, anyone have a solution for this?
POV: **you are struggling on a leetcode problem**
then you found neetcode have solve it
the BEST feeling ever
U video helps a lot
Can someone clarify why the tuple is being removed before returning the final result? What's the logic behind that line
you forget check if the test pass :>
Please run the code at the end to provide some relief to us OCD inflicted people :P
Is it not possible to not run dfs on a position in the board by checking if it equals the first letter in the word?
why in backtrack problems we remove what we did ? what you say cleaning step basically
How would you respond if a interviewer asked "How would you write this without the nested function?"