Leetcode - Word Search

Question

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.

This is abacktracking question.

Idea

• We solve this in basically the same way that we would if we didn’t have code
  • Find the starting letter and look at its neighbours for the next letter
  • We want to do this recursively now (search neighbours for the next letter) using dfs
• Base case:
  • If the length of our current word (i) is == to the length of our target word
    • True
  • If our current position is out of bounds
    • False
  • If the character we are at is not the next letter, or we visit a position in our seen set
    • False
• If we find a valid character, add our current position to our seen set
• Set our result to the OR of checking all four adjacent positions (recursively dfs on those positions)
• Remove our current position after the dfs calls since we are not longer visiting that position
• Return res
• Outside the dfs, call dfs in a nested for loop for every position, if dfs finds the word return true, otherwise return false

This is a brute force solution
Solution