Algorithm

Problem Name: 79. 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 &

Input

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

Output

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 &

Input

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

Output

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 &

Input

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

Output

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 &

Input

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

Output

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 & 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 & Input x – + cmd board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB" Output x – + cmd false Advertisements (adsbygoogle = window.adsbygoogle || []).push({}); Demonstration ```
``` #78 Leetcode Subsets Solution in C, C++, Java, JavaScript, Python, C# Leetcode #80 Leetcode Remove Duplicates from Sorted Array II Solution in C, C++, Java, JavaScript, Python, C# Leetcode ```
``` ```