123 · Word Search
Algorithms
Medium
Description
Given a 2D board and a string word, find if the string word exists in the grid.

The string 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.

The dimension of the letter matrix does not exceed 100, and the length of the string does not exceed 100.

Example
Example 1:

Input:

board = [“ABCE”,“SFCS”,“ADEE”]
word = “ABCCED”
Output:

true
Explanation:

[
A B C E
S F C S
A D E E
]
(0,0)->(0,1)->(0,2)->(1,2)->(2,2)->(2,1)

Example 1:

Input:

board = [“z”]
word = “z”
Output:

true
Explanation:

[ z ]
(0,0)

解法1：DFS+hashset。
很多小地方需要注意，特別是visited[][]數組什么時候clear掉。

class Solution {
public:/*** @param board: A list of lists of character* @param word: A string* @return: A boolean*/bool exist(vector<vector<char>> &board, string &word) {int m = board.size();if (m == 0) return word.empty();int n = board[0].size();string sol = "";for (int i = 0; i < word.size(); i++) {string tmpStr = word.substr(0, i + 1);s.insert(tmpStr);}vector<vector<bool>> visited;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {sol.clear(); //這里每次都要clear！不然后面的操作就append到s上面！visited.resize(m, vector<bool>(n, false));sol += board[i][j];if (check(board, word, sol, visited, i, j)) return true;}}return false;}
private:int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};set<string> s;bool check(vector<vector<char>> &board, string &word, string sol, vector<vector<bool>> &visited, int x, int y) {if (s.find(sol) == s.end()) return false;if (sol == word) {return true;}if (sol.size() >= word.size()) return false;visited[x][y] = true;for (int i = 0; i < 4; i++) {int newX = x + dx[i];int newY = y + dy[i];if (newX >= 0 && newX < board.size() && newY >= 0 && newY < board[0].size() && !visited[newX][newY]) {sol += board[newX][newY];if (check(board, word, sol, visited, newX, newY)) return true;else sol.pop_back();  //這一行重要！因為sol還要被for循環的其它i用到!}}visited[x][y] = false; //這一行重要，只有當dfs能夠一直往下進行，visited[][]才不用動，否則如果dfs中途退出，visited[][]要clear。不然就跟后面操作沖突！return false; //這里別忘了，不然默認可能會返回true!!!}
};

二刷：不需要set。每次比較當前位置的字符就可以了。

class Solution {
public:/*** @param board: A list of lists of character* @param word: A string* @return: A boolean*/bool exist(vector<vector<char>> &board, string &word) {int m = board.size();if (m == 0) return word.empty();int n = board[0].size();string sol = "";vector<vector<bool>> visited;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {sol.clear();visited.resize(m, vector<bool>(n, false));sol += board[i][j];if (check(board, word, sol, 0, visited, i, j)) return true;}}return false;}
private:int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};bool check(vector<vector<char>> &board, string &word, string sol, int pos, vector<vector<bool>> &visited, int x, int y) {if (sol[pos] != word[pos]) return false;if (sol == word) {return true;}//if (sol.size() >= word.size()) return false; //這一行不需要！如果不匹配早就返回了，匹配上面也會返回true。visited[x][y] = true;for (int i = 0; i < 4; i++) {int newX = x + dx[i];int newY = y + dy[i];if (newX >= 0 && newX < board.size() && newY >= 0 && newY < board[0].size() && !visited[newX][newY]) {sol += board[newX][newY];if (check(board, word, sol, pos + 1, visited, newX, newY)) return true;else sol.pop_back();  //這一行重要！因為sol還要被for循環的其它i用到!}}visited[x][y] = false; //這一行重要，只有當dfs能夠一直往下進行，visited[][]才不用動，否則如果dfs中途退出，visited[][]要clear。不然就跟后面操作沖突！return false;}
};

三刷: DFS+Trie
TBD

四刷:BFS
TBD