[00:01] looks intimidating, but it's really just pathfinding with one extra rule. You're goal is to build that word by moving through neighboring cells. You can move up, down, left, or right, but you can never reuse the same cell.
[00:16] path through the grid, but it's exponential, which is way too slow. Instead, you can find the first matching letter in the grid. Then from that cell, check all four neighbors for the next letter. Let's trace through this. Start
[00:29] at H. We need E next. Check each direction, and on the right side, there's E. So we move there. Now from E, we need L. So we look around and we find L down. Go ahead and take it. From this L, we need another L. We have two
[00:42] there's one to the right. So let's try the one below first. But now we need an O. And checking its neighbors, we don't find any Os. There isn't one there. So we just backtrack. Unmark that L and go back so we can try the other L
[00:56] instead. Now when we look for O again, it's right there on the right. We found it. Every step is just match the letter, explore four directions, and undo if it fails. That's backtracking. Just reverse when you hit a dead end. Learn more with
[01:08] interactive visualizations at hellointerview.com.