# Word Search

## Question

### Problem Statement

Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

#### Example

Given board =

[
"ABCE",
"SFCS",
]

• word = "ABCCED", -> returns true,
• word = "SEE", -> returns true,
• word = "ABCB", -> returns false.

## 题解

### Java

public class Solution {
/**
* @param board: A list of lists of character
* @param word: A string
* @return: A boolean
*/
public boolean exist(char[][] board, String word) {
if (board == null || board.length == 0 || board[0].length == 0) return false;
if (word == null || word.length() == 0) return false;

boolean[][] visited = new boolean[board.length][board[0].length];
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (dfs(board, word, visited, i, j, 0)) {
return true;
}
}
}

return false;
}

public boolean dfs(char[][] board, String word,
boolean[][] visited,
int row, int col,
int wi) {
// out of index
if (row < 0 || row > board.length - 1 ||
col < 0 || col > board[0].length - 1) {
return false;
}

if (!visited[row][col] && board[row][col] == word.charAt(wi)) {
// return instantly
if (wi == word.length() - 1) return true;
// traverse unvisited row and col
visited[row][col] = true;
boolean down = dfs(board, word, visited, row + 1, col, wi + 1);
boolean right = dfs(board, word, visited, row, col + 1, wi + 1);
boolean up = dfs(board, word, visited, row - 1, col, wi + 1);
boolean left = dfs(board, word, visited, row, col - 1, wi + 1);
// reset with false if none of above is true
visited[row][col] = up || down || left || right;
return up || down || left || right;
}

return false;
}
}


### 复杂度分析

DFS 最坏情况下遍历所有坐标点，二重 for 循环最坏情况下也全部执行完，故时间复杂度最差情况下为 $O(m^2n^2)$, 使用了visited矩阵，空间复杂度为 $O(mn)$, 当然这个可以优化到 $O(1)$.(原地更改原 board 数组字符内容)。