Word Search In C,CPP,JAVA,PYTHON,C#,JS

/ DSA / By
Spread the love
Close-up of HTML code highlighted in vibrant colors on a computer monitor.

Problem Statement: Word Search

Given an m x n board of characters and a string word, write a function to check if the word exists in the board. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example

Example 1:

  • Input:plaintextCopy codeboard = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] word = "ABCCED"
  • Output: trueExplanation: The word "ABCCED" can be constructed from the board by starting at board[0][0], then moving right to board[0][1], down to board[1][1], down to board[2][1], and right to board[2][2].

Example 2:

  • Input:plaintextCopy codeboard = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] word = "SEE"
  • Output: trueExplanation: The word "SEE" can be constructed from the board by starting at board[2][0], then moving right to board[2][1], and up to board[1][1].

Example 3:

  • Input:plaintextCopy codeboard = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] word = "ABCB"
  • Output: falseExplanation: The word "ABCB" does not exist on the board, because the letter ‘B’ at board[0][1] is used twice, and we cannot use the same cell twice.

Approach

We can solve this problem using Depth First Search (DFS) to explore possible paths for the word. The idea is to start from each cell and check whether the word can be formed by exploring adjacent cells recursively.

Steps:

  1. DFS Search: For each character in the board, we will start a DFS search if it matches the first character of the word.
    • If the current character matches the corresponding character in the word, recursively search for the next character in the adjacent cells (up, down, left, right).
    • If all characters in the word are matched, return true.
  2. Backtracking: Since each cell can be used only once, mark the current cell as visited during the DFS search and unmark it once the search is complete for that path (backtrack).
  3. Boundary Check: Ensure that we don’t go out of bounds when searching adjacent cells.

Time and Space Complexity

  • Time Complexity: The time complexity is O(m * n * 4^L), where m is the number of rows, n is the number of columns, and L is the length of the word. This is because, in the worst case, we explore every possible cell and recursively check all adjacent cells.
  • Space Complexity: The space complexity is O(m * n) due to the recursion stack (in the worst case, the recursion depth can be the number of cells in the board).

Code Implementations

1. C++

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if (board.empty() || word.empty()) return false;
        
        int m = board.size(), n = board[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (dfs(board, word, i, j, 0, visited)) return true;
            }
        }
        return false;
    }

private:
    bool dfs(vector<vector<char>>& board, string& word, int i, int j, int index, vector<vector<bool>>& visited) {
        if (index == word.size()) return true;  // All characters are found

        if (i < 0 || j < 0 || i >= board.size() || j >= board[0].size() || visited[i][j] || board[i][j] != word[index]) {
            return false;
        }

        visited[i][j] = true;  // Mark as visited
        
        // Explore in all four directions
        bool result = dfs(board, word, i + 1, j, index + 1, visited) ||
                      dfs(board, word, i - 1, j, index + 1, visited) ||
                      dfs(board, word, i, j + 1, index + 1, visited) ||
                      dfs(board, word, i, j - 1, index + 1, visited);

        visited[i][j] = false;  // Unmark for backtracking
        
        return result;
    }
};

int main() {
    Solution sol;
    vector<vector<char>> board = {
        {'A','B','C','E'},
        {'S','F','C','S'},
        {'A','D','E','E'}
    };
    string word = "ABCCED";
    cout << boolalpha << sol.exist(board, word) << endl;  // Output: true
    return 0;
}

2. Java

public class Solution {
    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0 || word == null || word.length() == 0) return false;

        int m = board.length, n = board[0].length;
        boolean[][] visited = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(board, word, i, j, 0, visited)) return true;
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, String word, int i, int j, int index, boolean[][] visited) {
        if (index == word.length()) return true;  // All characters found

        if (i < 0 || j < 0 || i >= board.length || j >= board[0].length ||
            visited[i][j] || board[i][j] != word.charAt(index)) {
            return false;
        }

        visited[i][j] = true;  // Mark as visited

        // Explore four directions
        boolean result = dfs(board, word, i + 1, j, index + 1, visited) ||
                         dfs(board, word, i - 1, j, index + 1, visited) ||
                         dfs(board, word, i, j + 1, index + 1, visited) ||
                         dfs(board, word, i, j - 1, index + 1, visited);

        visited[i][j] = false;  // Unmark for backtracking

        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        char[][] board = {
            {'A','B','C','E'},
            {'S','F','C','S'},
            {'A','D','E','E'}
        };
        String word = "ABCCED";
        System.out.println(sol.exist(board, word));  // Output: true
    }
}

3. Python

class Solution:
    def exist(self, board, word):
        if not board or not word:
            return False
        
        m, n = len(board), len(board[0])
        visited = [[False] * n for _ in range(m)]

        def dfs(i, j, index):
            if index == len(word):
                return True
            if i < 0 or j < 0 or i >= m or j >= n or visited[i][j] or board[i][j] != word[index]:
                return False

            visited[i][j] = True  # Mark as visited
            # Explore all four directions
            result = (dfs(i + 1, j, index + 1) or
                      dfs(i - 1, j, index + 1) or
                      dfs(i, j + 1, index + 1) or
                      dfs(i, j - 1, index + 1))

            visited[i][j] = False  # Unmark for backtracking
            return result

        for i in range(m):
            for j in range(n):
                if dfs(i, j, 0):
                    return True
        return False

# Example usage
board = [
    ['A','B','C','E'],
    ['S','F','C','S'],
    ['A','D','E','E']
]
word = "ABCCED"
sol = Solution()
print(sol.exist(board, word))  # Output: True

4. C#

public class Solution {
    public bool Exist(char[][] board, string word) {
        if (board == null || board.Length == 0 || word == null || word.Length == 0) return false;

        int m = board.Length, n = board[0].Length;
        bool[,] visited = new bool[m, n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (DFS(board, word, i, j, 0, visited)) return true;
            }
        }
        return false;
    }

    private bool DFS(char[][] board, string word, int i, int j, int index, bool[,] visited) {
        if (index == word.Length) return true;  // All characters found

        if (i < 0 || j < 0 || i >= board.Length || j >= board[0].Length ||
            visited[i, j] || board[i][j] != word[index]) {
            return false;
        }

        visited[i, j] = true;  // Mark as visited

        // Explore all four directions
        bool result = DFS(board, word, i + 1, j, index + 1, visited) ||
                      DFS(board, word, i - 1, j, index + 1, visited) ||
                      DFS(board, word, i, j + 1, index + 1, visited) ||
                      DFS(board, word, i, j - 1, index + 1, visited);

        visited[i, j] = false;  // Unmark for backtracking

        return result;
    }
}

class Program {
    static void Main() {
        var board = new char[][] {
            new char[] {'A','B','C','E'},
            new char[] {'S','F','C','S'},
            new char[] {'A','D','E','E'}
        };
        string word = "ABCCED";
        var sol = new Solution();
        Console.WriteLine(sol.Exist(board, word));  // Output: True
    }
}

5. JavaScript

var exist = function(board, word) {
    if (!board || !word) return false;

    const m = board.length, n = board[0].length;
    const visited = Array.from({ length: m }, () => Array(n).fill(false));

    function dfs(i, j, index) {
        if (index === word.length) return true;
        if (i < 0 || j < 0 || i >= m || j >= n || visited[i][j] || board[i][j] !== word[index]) {
            return false;
        }

        visited[i][j] = true;  // Mark as visited

        // Explore four directions
        const result = dfs(i + 1, j, index + 1) ||
                       dfs(i - 1, j, index + 1) ||
                       dfs(i, j + 1, index + 1) ||
                       dfs(i, j - 1, index + 1);

        visited[i][j] = false;  // Unmark for backtracking
        return result;
    }

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (dfs(i, j, 0)) return true;
        }
    }
    return false;
};

// Example usage
const board = [
    ['A','B','C','E'],
    ['S','F','C','S'],
    ['A','D','E','E']
];
const word = "ABCCED";
console.log(exist(board, word));  // Output: true

6.C

#include <stdio.h>
#include <stdbool.h>

#define MAX_ROWS 100
#define MAX_COLS 100

// Directions: Up, Down, Left, Right
int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

bool dfs(char board[MAX_ROWS][MAX_COLS], int m, int n, const char* word, int wordIndex, int i, int j, bool visited[MAX_ROWS][MAX_COLS]) {
    // Base condition: if we've matched the entire word
    if (word[wordIndex] == '\0') {
        return true;
    }

    // If out of bounds or current cell doesn't match the word character or already visited, return false
    if (i < 0 || j < 0 || i >= m || j >= n || visited[i][j] || board[i][j] != word[wordIndex]) {
        return false;
    }

    // Mark the current cell as visited
    visited[i][j] = true;

    // Explore all 4 possible directions (Up, Down, Left, Right)
    for (int d = 0; d < 4; d++) {
        int newRow = i + directions[d][0];
        int newCol = j + directions[d][1];
        
        // Recursively search the next character in the word
        if (dfs(board, m, n, word, wordIndex + 1, newRow, newCol, visited)) {
            return true;
        }
    }

    // Unmark the current cell as visited for backtracking
    visited[i][j] = false;
    return false;
}

bool exist(char board[MAX_ROWS][MAX_COLS], int m, int n, const char* word) {
    if (!board || !word) return false;

    // Create a visited array to mark cells we've already visited
    bool visited[MAX_ROWS][MAX_COLS] = {{false}};

    // Try to find the word starting from every cell in the board
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            // Start DFS search if the first character matches
            if (board[i][j] == word[0] && dfs(board, m, n, word, 0, i, j, visited)) {
                return true;
            }
        }
    }
    return false;
}

int main() {
    char board[MAX_ROWS][MAX_COLS] = {
        {'A', 'B', 'C', 'E'},
        {'S', 'F', 'C', 'S'},
        {'A', 'D', 'E', 'E'}
    };

    int m = 3, n = 4;
    const char* word = "ABCCED";

    if (exist(board, m, n, word)) {
        printf("Word found\n");
    } else {
        printf("Word not found\n");
    }

    return 0;
}

Conclusion

The Word Search problem is a typical backtracking problem that can be solved efficiently using DFS with backtracking. By marking cells as visited during the search and backtracking when necessary, we can explore all possible paths for the word in the grid.