Word Search Board

Back to home

𝑻𝒂𝒃𝒍𝒆 𝒐𝒇 𝑪𝒐𝒏𝒕𝒆𝒏𝒕

Problem Statement: Word Search Board
Approach: Using DFS

Logicmojo - Updated Aug 28, 2021

Problem Statement: Word Search Board

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.

Examples: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"

Output: True

Approach: Using DFS

This is an advanced problem. This problem uses DFS approach along with backtracking. (The Fact that the visited is marked as True before getting into recursion inside the function and again marking it as False if we have not gotten the answer is the reason why this problem is a backtracking problem.)

Algorithm:

1. You have to try each location in the board is as a strating point. So 2d loop at the start is necessary.

2. We start from each character, and try to move in each possible direction until we can match the complete word. We use DFS for this.

3. When we know that we have seen the complete word, we mark found in global variable, and return True from main function.

4. Note that you cannot mark same location more than once so, we have to use visited 2d array to mark it as visited.

5. At times we may have gone in a wrong path and due to this we would have mark some locations useless as visited, we have unvisit them, if we see that id haven't lead to the answer. This is why this problem is backtracking + DFS.

C++ Implementation:

bool exist(vector<vector<char>>& board, string word) {
    for (unsigned int i = 0; i < board.size(); i++) 
        for (unsigned int j = 0; j < board[0].size(); j++) 
            if (dfs(board, i, j, word))
                return true;
    return false;
}

bool dfs(vector<vector<char>>& board, int i, int j, string& word) {
    if (!word.size())
        return true;
    if (i<0 || i>=board.size() || j<0 || j>=board[0].size() || board[i][j] != word[0])  
        return false;
    char c = board[i][j];
    board[i][j] = '*';
    string s = word.substr(1);
    bool ret = dfs(board, i-1, j, s) || dfs(board, i+1, j, s) || dfs(board, i, j-1, s) || dfs(board, i, j+1, s);
    board[i][j] = c;
    return ret;
}

Python Implementation:

class Solution:
    def exist(self, board, word):
        m = len(board)
        n = len(board[0])
        visited = [[False for _ in range(n)] for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if board[i][j] == word[0]:
                    if self.valid(board, word, i, j, m, n, visited, 0):
                        return True
        
        return False
    def valid(self, board, word, i, j, m, n, visited, pos):
        if len(word) == pos:
            return True
        if i < 0 or i == m or j < 0 or j == n or visited[i][j] or word[pos] != board[i][j]:
            return False
        visited[i][j] = True
        res = self.valid(board, word, i, j + 1, m, n, visited, pos + 1)\
 or self.valid(board, word, i, j - 1, m, n, visited,pos + 1) or \
self.valid(board, word, i + 1, j, m, n, visited, pos + 1)\
 or self.valid(board, word, i - 1, j, m, n, visited, pos + 1)
        visited[i][j] = False
        return res
ob1 = Solution()
print(ob1.exist([["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"))

Time Complexity: O(N * 3 ^ L). N is total number of cells in the board. L is the length of the word. 3 power because, we will have three sides to expand each time.

Space Complexity: O(m * n), because in worst case, the whold word length stack space would be used.

With this article at Logicmojo, you must have the complete idea of solving Word Search Board problem.