79. Word Search Leetcode Solution

Word Search Leetcode Problem :

Given an m x n grid of characters board and a string word, return true if 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.

jump game leetcode

Word Search Leetcode Solution :

Constraints :

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board and word consists of only lowercase and uppercase English letters.

Example 1:

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

Example 2:

  • Input: board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCB”
  • Output: false

Intuition :

  • Basic backtracking problem on a matrix, usually we call it a grid search backtracking problem.
  • The main idea is to try all possible valid solution
  • by this i mean, if the current character is same as the one in the trgt, then try all his neighbours (left, right, up, down).
  • if not valid, then just return false.

Approach :

  1. Backtracking logic start by marking that we are going to take the current character.
  2. Then you have to visit the four neighbours of the current character under one main condition.
    1. the current character is a valid character, and this mean, that the current character in the board is same as the character that should be added now, and to know this i used this logic
         if (board[i][j] == trgt[s.length()])
  3. now you can visit the 4 neighbours either manualy by incrementing indices by yourself .
  4. or just use the compact logic, by creating two index vectors dx and dy, and just use one loop to iterate over the 4 neighbours as you can see in the code This is the best practice.
  5. Note one thing, that we are just searching for a word, so if we can construct it from one way, we do not need to try others, so just return if you got atleast one true.
  6. Then at the end, just apply the backtracking logic, by marking this character as untaken again, then return false.

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Code :

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription