• Customer Support: admin@thealgorists.com
  • Feedback: We are listening to your every feedback, and taking action to constantly improve your learning experience. If you have any feedback, please use this form: https://thealgorists.com/Feedback.



Problem Statement:


Given an m x n board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cells, where "adjacent" cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:


Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"

Output: true

Example 2:


Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

Example 3:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false

Solution:


  • NOTE: I highly recommend going through the Backtracking chapters in the order they are given in the Index page to get the most out of it and be able to build a rock-solid understanding.


If you have gone through Backtracking problems discussed previously, you already know how to solve this problem. For every candidate cell we would search all eligible adjacent cells, which is nothing but exhaustive searching. I won't go into details since we have already discussed that multiple times in previous chapters.

I would like to point out an important aspect that we need to take care of and often easy problems like this are asked in interviews to see how detail-oriented you are and if you are able to think of important yet simple things like this which would ultimately pay the most critical part in designing a correct algorithm and bug-free code: so the aspect here is that we cannot include a cell more than once while searching for a word. While searching for a word if a cell (x, y) is already visited as part of the current backtrack path (think of it as a path in the 'backtrack tree') we should not re-visit that again. Example: input: [["a", "a"]], string to search = "aaa", You cannot visit cell (0, 0) and (0, 1) and then again (0, 0) and say you found "aaa". Because (0, 0) is already visited you cannot revisit it.

Once you have figured this out, the rest would be super simple if you follow our backtracking template.

Java Code:



This is a Premium content.
Please subscribe to Algorithms course to access the code.




Python Code:



This is a Premium content.
Please subscribe to Algorithms course to access the code.





Don't forget to take in-depth look at the other backtracking problems because that is what would make you comfortable with using the backtracking template and master the art of Backtracking:


The above content is written by:

Abhishek Dey

Abhishek Dey

A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave