79. Word Search ------- M ！！！！！

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?

A:

 ----------------------------------  3 rd pass ,  用一个2D array 记录是否visit过---------- 然后就是简单的dfs了----------------和第二遍一样，但是，没有这里，检测了输入m,n是否为0 的情况，因此，多写了几行。------------

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        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, visited, word, 0, i, j))
                    return true;
        return false;
    }

private:
    vector<vector<int>> Diff = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
    bool dfs(vector<vector<char>>& board, vector<vector<bool>>& visited,
             string word, int idx, int row, int col) {
        int m = board.size(), n = board[0].size();
        if (!visited[row][col] && board[row][col] == word[idx]) {
            if (idx == word.length() - 1)
                return true;
            visited[row][col] = true;
            for (auto diff : Diff) {
                int x = row + diff[0], y = col + diff[1];
                if (x >= 0 && x < m && y >= 0 && y < n) {
                    if (dfs(board, visited, word, idx + 1, x, y))
                        return true;
                }
            }
            visited[row][col] = false;
        }
        return false;
    }
};

然而，上面的代码， 超时了

仔细研究。 发现我们
1:  忘记mark string word as &
2:  can skip the use of visited[][] 2D array.  (and use special character in board[][] instead.)
3:  Not pruning failed paths early enough.
  Not inlining checks efficiently.

下面是修改后的代码
class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size(), n = board[0].size();
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (dfs(board, word, 0, i, j))
                    return true;
        return false;
    }
private:
    bool dfs(vector<vector<char>>& board, const string& word, int idx, int row,
             int col) {
        int m = board.size(), n = board[0].size();
        if (row < 0 || row >= m || col < 0 || col >= n || board[row][col] != word[idx])
            return false;
        if (idx == word.length()-1)
            return true;
        char tmp = board[row][col];
        board[row][col] = '#'; // mark as visited
        bool found = dfs(board, word, idx + 1, row - 1, col) ||
                     dfs(board, word, idx + 1, row + 1, col) ||
                     dfs(board, word, idx + 1, row, col - 1) ||
                     dfs(board, word, idx + 1, row, col + 1);
        board[row][col] = tmp;
        return found;
    }
};

错误：

在dfs中，我们已经假设了word不为空，就需要在match当前char之后，再看现在是否start 位置还没出界-------------------






 ------------------------------------------- 1 st  pass ---------------------------------------------------------------
增强的 DFS ,
思路就是，通过另一个visitedBoard来记录该节点是否所有的neighbor都被visited 过。如果没有，则增加一个，如果有。 则pop出来该节点。并将其父节点（stack.peak()） 的visitBoard 的数量增加1.
-----------------
一个关键的问题就是：我们dfs的时候，设置了停止条件是： start>word.length();  但是这样是不对的。
因为，有可能我们的下标没有可能出界的。例如输入时“s”，"s"。
因此，我们要检测是否是最后一个char






Mistakes:
1：   findStringIndex的考虑的时候， 例如当问题中给出的例子，”ABCB“的时候， 当找到C的时候， findStringIndex 的值是3了， 而，在我们别的变量里面，都是index, 而不是match的数量，因此，我们这里应该是2的。 ------------------------------哎，你个糊涂蛋，------------
                     if( lastFindCharIndex >= word.length() -1){// if match the last char
                        return true; // we just find the whole word
                    }
你这里，是考虑的当已经找到了最后一个的情况，   然后，我们这时候，在下面的四种情况中，是 加了1 的，      那么，就word.length() 就不应该减一啊。
-------------哦， 当初想减一，是考虑到，后面的4种情况监测的时候，  要加1 啊
晕，你SB，  上面全错了， 那样写是对的，只是因为，题目要求 may NOT  use the same letter more than once. --------------------看题不谨慎啊！！！！！！！！
2：在利用tmpBoard的时候，忘了把第一个字母全部变成neverUsedChar,  导致输入{"aa"} "aaa"的时候，结果是find。

3: 当一条路走不通的时候，应该把走过的路，都回溯成原来的样子， 以待别走法。

4： 不能用BFS， 那样的话， 就会先把周围match的点的颜色先该了。
5： 自己还是因为，对DFS的理解不够深入导致，回去多看看类似的DFS，BFS的 题目吧。


Learned:
1: ArrayList<int[]> firstIndexes = new ArrayList<int[]>();  这样是可以的， 而不是非得用Integer 取代int. (自己是受以前的代码的影响）
2: