79.Word_Search(Medium).md

79. Word Search (Medium)

Date and Time: Jul 27, 2024, 18:04 (EST)

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

Date	Stopwatch	Y/N	Feedback
Jul 8, 2025	21m 48s	Y	New Approach in DFS

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.

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

Edge case:

Input: board = [["C","A","A"],["A","A","A"],["B","C","D"]],
word = "AAB"

Output: true

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.

KeyPoints:

We start from the beginning of the matrix[0][0], and increment c, r to recursively call the backtrack() to find if we start from matrix[r][c] can lead to a path that can form word.

As usual, we find the base cases in backtrack(), when i == len(word) we should return True. We check for false conditions by checking if r, c are out of bound, or matrix[r][c] != word[i], or matrix[r][c] in path. If we pass these conditions, we know [r, c] is the right position, and we check [r, c]'s neighbors. If its neighbors are all wrong, we should remove current [r, c] from path(), so we can move on to [r, c + 1] and it won't prevent us to check [r, c + 1]'s left neighbor [r, c].

path() is used to keep track of the starting position and the positions from the starting position. If we follow the path and that path isn't the right path, we should remove all the positions we added to path(), so we should path.remove((r, c)) right after res.

My DFS Solution:

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        # Q: Check if we can form word from board
        # S: Run DFS/Backtrack on board, if a letter match in word, check the next grid on 4 directions and add pos into visited()
        # Explore: 1. pos not in visited. 2. board[r][c] == word[j]
        # Return True when j == len(word)
        # TC: O(m*n*(3^L)), L=len(word), SC: O(L)

        rows, cols = len(board), len(board[0])
        visited = set()
        directions = [[-1, 0], [1, 0], [0, 1], [0, -1]]
        def dfs(r, c, j):
            if j == len(word):
                return True
            visited.add((r, c))
            for dr, dc in directions:
                new_r, new_c = r + dr, c + dc
                if new_r in range(rows) and new_c in range(cols) and (new_r, new_c) not in visited and board[new_r][new_c] == word[j]:
                    if dfs(new_r, new_c, j+1):
                        return True
            visited.remove((r, c))
            return False
        # Traverse board to find word[0]
        for r in range(rows):
            for c in range(cols):
                if board[r][c] == word[0]:
                    if dfs(r, c, 1):
                        return True
        return False

Time Complexity: $O(m * n * 3^{L-1})$, first $O(m*n)$ to traverse board, then to find the second letter in word, we have 3 choices to choose after the first letter, so we have $O(3^{L-1})$ to check three neighbors for the rest of letters.
Space Complexity: $O(L)$, in the worst case, we only need to save the positions of length of word.

Python Solution:

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        path = set()
        rows, cols = len(board), len(board[0])
        def backtrack(r, c, i):
            if i == len(word):
                return True
            # Check False conditions for (r, c)
            if (r < 0 or c < 0 or r >= rows or c >= cols or (r, c) in path
                or board[r][c] != word[i]):
                return False
            # Otherwise, (r, c) is true and we search its neighbor
            path.add((r, c))
            # Search l,r,t,b for word[i+1]
            res = (backtrack(r, c-1, i+1) or backtrack(r, c+1, i+1)
                or backtrack(r-1, c, i+1) or backtrack(r+1, c, i+1))
            path.remove((r, c))
            return res

        for r in range(rows):
            for c in range(cols):
                if backtrack(r, c, 0):
                    return True
        return False

Time Complexity: $O(m * n * 4^l)$, m * n is the area of the matrix, 4^l is the length of word because we are searching each character of word's four directions.
Space Complexity: $O(\text{len(word)})$, because we only need to store all the cells of word in path().

Java Solution:

class Solution {
    public boolean exist(char[][] board, String word) {
        int rows = board.length;
        int cols = board[0].length;
        Set<String> set = new HashSet<>();
        
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (backtrack(board, word, r, c, 0, set)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    private boolean backtrack(char[][] board, String word, int r, int c, int index, Set<String> set) {
        if (index == word.length()) { return true; }
        String pair = r + "," + c;
        if (r < 0 || c < 0 || r >= board.length || c >= board[0].length || board[r][c] != word.charAt(index) || set.contains(pair)) {
            return false;
        }
        set.add(pair);
        boolean found = (backtrack(board, word, r+1, c, index+1, set) || 
                        backtrack(board, word, r-1, c, index+1, set) ||
                        backtrack(board, word, r, c+1, index+1, set) ||
                        backtrack(board, word, r, c-1, index+1, set));
        set.remove(pair);
        return found;
    }
}

C++ Solution:

In C++, we use vector<vector<bool>> visited(rows, vector<bool>(cols, false)); to define a "set()", because it will exceed time limit if we use set().

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int rows = board.size();
        int cols = board[0].size();
        // set<pair<int, int>> set;
        vector<vector<bool>> visited(rows, vector<bool>(cols, false));
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (backtrack(board, word, r, c, 0, visited)) {
                    return true;
                }
            }
        }
        return false;
    }
private:
    bool backtrack(vector<vector<char>>& board, string word, int r, int c, int index, vector<vector<bool>>& visited) {
        if (index == word.size()) { return true; }
        if (r < 0 || c < 0 || r >= board.size() || c >= board[0].size() || board[r][c] != word[index] || visited[r][c]) {
            return false;
        }
        visited[r][c] = true;
        bool found = (backtrack(board, word, r-1, c, index+1, visited) ||
                backtrack(board, word, r+1, c, index+1, visited) ||
                backtrack(board, word, r, c+1, index+1, visited) ||
                backtrack(board, word, r, c-1, index+1, visited));
        visited[r][c] = false;
        return found;
    }
};