Algorithm

Problem Name: 79. Word Search

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

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

 

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.

 

Follow up: Could you use search pruning to make your solution faster with a larger board?

 

Code Examples

#1 Code Example with C Programming

Code - C Programming


const int offset[][2] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
 
bool validate(int r, int c, int *visited, char **board, int rowsz, int colsz, char *word) {
  int i, j, k;

  if (board[r][c] != *word) return false;
  if (!*(word + 1)) return true;

  visited[r * colsz + c] = 1;

  for (k = 0; k  <  4; k ++) {
        i = r + offset[k][0];
        j = c + offset[k][1];
        if (i >= 0 && i  < = rowsz - 1 &&
            j >= 0 && j <= colsz - 1 &&
            !visited[i * colsz + j]) {
            if (validate(i, j, visited, board, rowsz, colsz, word + 1)) return true;   
      }
    }

  visited[r * colsz + c] = 0;

  return false;
}
bool exist(char** board, int boardRowSize, int boardColSize, char* word) {
  int i, j, *visited;
  bool ret = false;

  visited = calloc(boardRowSize * boardColSize, sizeof(int));

  for (i = 0; !ret && i  <  boardRowSize; i ++) {
        for (j = 0; !ret && j  <  boardColSize; j ++) {
            if (validate(i, j, visited, board, boardRowSize, boardColSize, word)) ret = true;
      }
    }

  free(visited);
  return ret;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"

Output

x
–
+
cmd
true

#2 Code Example with C++ Programming

Code - C++ Programming


class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if(board.size() == 0|| word.size() == 0) return true;
        bool find = false;
        vector<vector < int>>visited(board.size(), vector<int>(board[0].size(),0));
        for(int i = 0 ; i  <  board.size(); i++)
            for(int j = 0; j  <  board[0].size(); j++){
                if(board[i][j] == word[0]){
                     find = backtrack(i, j, board, word, visited);
                     if(find) return find;
                }
            }
        return find;
    }
    
    bool backtrack(int i, int j, vector < vector<char>>& board, string word, vector < vector<int>>& visited){
        if(word.size() == 0> return true;
        if(i  <  0 || i > board.size() - 1 || j < 0 || j > board[0].size() - 1) return false;
        if(visited[i][j]) return false;
        bool find = false;
        if(board[i][j] == word[0]){
            word.erase(word.begin());
            visited[i][j] = 1;
            find = backtrack(i-1,j,board,word,visited) || backtrack(i,j-1,board,word,visited) 
                || backtrack(i+1,j,board,word,visited) || backtrack(i,j+1,board,word,visited);
            visited[i][j] = 0;
        }
       return find;
    }
};
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"

Output

x
–
+
cmd
true

#3 Code Example with Java Programming

Code - Java Programming


class Solution {
    
    private static final int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i  <  m; i++) {
            for (int j = 0; j  <  n; j++) {
                if (isFound(board, word, 0, i, j, m, n)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    private boolean isFound(char[][] board, String word, int idx, int row, int col, int m, int n) {
        if (idx == word.length()) {
            return true;
        }
        if (row  <  0 || col < 0 || row >= m || col >= n || board[row][col] != word.charAt(idx)) {
            return false;
        }
        board[row][col] ^= 256;
        boolean result = false;
        for (int[] dir : DIRS) {
            result = result || isFound(board, word, idx + 1, row + dir[0], col + dir[1], m, n);
        }
        board[row][col] ^= 256;
        return result;
    }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"

Output

x
–
+
cmd
true

#4 Code Example with Javascript Programming

Code - Javascript Programming


const exist = function(board, word) {
  const dirs = [[0, 1], [0, -1], [-1, 0], [1, 0]];
  for (let j = 0; j  <  board.length; j++) {
    for (let i = 0; i  <  board[0].length; i++) {
      let res = dfs(board, i, j, dirs, word, 0);
      if (res) {
        return true;
      }
    }
  }
  return false;
};

function dfs(board, x, y, dirs, word, start) {
  if (start >= word.length) return true;
  if (x  <  0 || y < 0 || x >= board[0].length || y >= board.length) return false;
  if (word[start] !== board[y][x] || board[y][x] === "#") return false;

  let res = false;
  let c = board[y][x];
  board[y][x] = "#";
  for (let el of dirs) {
    let posx = x + el[0];
    let posy = y + el[1];
    res = res || dfs(board, posx, posy, dirs, word, start + 1);
    if (res) return true;
  }
  board[y][x] = c;

  return false;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"

Output

x
–
+
cmd
true

#5 Code Example with Python Programming

Code - Python Programming


class Solution:
    def exist(self, board, word):
        m, n, o = len(board), len(board and board[0]), len(word)
        def explore(i, j, k, q):
            for x, y in ((i - 1, j), (i, j - 1), (i + 1, j), (i, j + 1)):
                if k>=o or (0<=x
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"

Output

x
–
+
cmd
false

#6 Code Example with C# Programming

Code - C# Programming


namespace LeetCode
{
    public class _079_WordSearch
    {
        public bool Exist(char[][] board, string word)
        {
            int R = board.Length, C = board[0].Length;
            var used = new bool[R, C];

            int i, j;
            for (i = 0; i  <  R; i++)
                for (j = 0; j  <  C; j++)
                    if (Exist(board, word, 0, i, j, used))
                        return true;

            return false;
        }

        private bool Exist(char[][] board, string word, int index, int row, int column, bool[,] used)
        {
            int R = board.Length, C = board[0].Length;
            if (board[row][column] != word[index] || used[row, column]) { return false; }

            used[row, column] = true;
            index++;

            if (index == word.Length) { return true; }

            if ((row + 1  <  R && Exist(board, word, index, row + 1, column, used)) ||
                (row > 0 && Exist(board, word, index, row - 1, column, used)) ||
                (column + 1 < C && Exist(board, word, index, row, column + 1, used)) ||
                (column > 0 && Exist(board, word, index, row, column - 1, used)))
            {
                return true;
            }

            used[row, column] = false;
            return false;
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"

Output

x
–
+
cmd
false
Advertisements

Demonstration

Previous
#78 Leetcode Subsets Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#80 Leetcode Remove Duplicates from Sorted Array II Solution in C, C++, Java, JavaScript, Python, C# Leetcode