79. Word Search

 

Description:

https://leetcode.com/problems/word-search/

We should go through every single matrix using Brute Force, backtracking, backtracking with recursively. 

Solution:

O(m * n * dfs(n^4)) solution

We should go through the whole matrix. It is gonna be brute force search. This method makes the function dfs to make a path to search whole matrix. We have a materials length of Matrix(M, N), and the set of path to store our path in the matrix. Let's see the dfs function.

 

In dfs function, we have a count variable "i".

dfs suppose that if the count variable end with length of word, it is true there is a set of word in matrix.

But, if  the search out of range, no word in matrix, and search the same cell again return false. So, we can stop the function and return false while recursiving.

Since we try to make recursive function, we return dfs again as a variable "res".

path is the set of we have been tracked, so it figures it out which cell we have been through.

Then, we are gonna see the up, down, left, right cell recursively.

If one of the four cell is true, then proceed the recursive function.