79. Word Search

Word Search (Medium) Given an m x n board of letters and a target word, we need to determine whether the word can be built by moving through adjacent cells horizontally or vertically. The key idea is to try every cell as a starting point, then use DFS + backtracking to see whether we can build the word one character at a time. While exploring one path, we mark cells as visited so we do not reuse the same cell in that path. If a path fails, we backtrack by removing that cell from the visited set and try another direction. Backtracking / DFS Solution: Time Complexity: O(m * n * 3^len(word)) Space Complexity: O(len(word)) extra space We try each board cell as a possible starting point. From a valid starting cell, the recursive function checks whether the current cell matches the current character of the word. If not, that path fails immediately. If it does match, we temporarily add that cell to visit and explore 4 directions. The reason we remove the cell afterward is that it should only be blocked for the current path, not for future paths.