LeetCode 79. Word Search（非递归算法）

上次算法实验课的时候，助教问我可不可以用非递归的方式实现，回去之后折腾了好一会儿终于在LeetCode上AC了我的非递归版本，在这里分享一下。

题目：

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:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

题目大意：

给一个char型二维数组和一个word字符串，寻找网格中是否含有word字符串，只能通过相邻（垂直或者水平）的格子连接～

分析：

此题的要求是在二维的情况下搜索解是否存在，如果使用DFS（深度优先搜索）算法可以很直观明了且迅速得到解。

DFS算法的基本思路是，当搜索过程遇到分岔路口时，首先选择其中一个路口进入，如果进去之后可以找到解，在此题中就可以直接返回true，声明解是存在的；如果进去之后没有找到解，那么还回到这个分岔路口，选择另外一个路口进入，继续搜解。如果每个路口都进去过了，而且都没有搜到解，那么就可以说解是不存在的。 我们将二维数组中的每个点都尝试着作为起点，从这一点试着向上下左右四个方向拓展，一个方向里搜不到解就搜另一个方向，如果四个方向都搜不到解就说明以此点为起点是搜不到解的，换个起点试试~

递归算法可以看看柳神的blog，上次算法实验课的时候，助教问我可不可以用非递归的方式实现，回去之后折腾了好一会儿终于在LeetCode上AC了我的非递归版本，在这里分享一下。

首先，非递归算法的基本思路和递归算法大致相同，在搜索过程中遇到分岔路口的时候，我们都会选择一个路口进入。当我们使用递归算法时，操作系统会为我们保留这个岔路口的信息，如果我们选错了路，还可以方便的回到这个岔路口；而非递归算法就需要我们自己手动保存分岔路口的信息了。我们使用栈这个数据结构来保存分岔路口的信息，因为栈的先进后出的特性与这种情况十分相符，使用这种特性的目的是为了当做错了某种选择时，我们可以方便的将状态回退。

举个栗子🌰：比如今天出门要给自己搭配一套衣服，我们要选择衬衫，卫衣以及外套这三件衣服。我们的选择有黑衬衫和白衬衫、红卫衣和绿卫衣、蓝外套和粉外套，然而我的衣品不怎么样，不知道怎么穿才好看，那我只能去尝试一下。我先穿上黑衬衫，再穿上红卫衣，最后穿上蓝外套，对镜子一看，怎么这么丑！肯定是外套的问题，这时我需要换外套，就脱下现在的外套，回到穿着卫衣和衬衫的状态，然后穿上粉外套。对镜子一看，我去，更丑了！肯定是卫衣的问题，那么我要回到选择卫衣的状态，我就需要把外套脱下，再把卫衣脱下，此时只穿着衬衫，这时我就可以重新选择卫衣了。把衣服脱下就是一种状态回退，这种状态回退总是遵循先进后出的顺序，所以使用栈来保存状态回退点再合适不过了。

接下来直接进入coding时间。我们需要先准备好一个栈stack<unsigned long> 以及访问标记数组vector<vector<bool>> visited;

第一步先把主框架exist函数搭好，之后main函数里就直接调用exist函数得出结果。内部init函数是一个将栈和visited访问标志数组初始化的函数。初始化完成之后，就尝试将board数组中的每个元素设为起点，进行dfs搜索。如果搜索到了就直接返回true；如果搜索完所有点也搜不到就返回false。

bool exist(vector<vector<char> > &board, string word) {
  init(board);
  for (int i = 0; i < board.size(); i++) {
    for (int j = 0; j < board[0].size(); j++) {
      if (DFSTraverse(board, word, i, j))
        return true;
    }
  }
  return false;
}
void init (vector<vector<char> > &board) {
  visited.resize(board.size(), vector<bool>(board[0].size()));
  dirc.resize(board.size(), vector<int>(board[0].size()));
  return;
}

随后就要编写DFSTraverse函数，这样声明函数bool DFSTraverse (vector<vector<char> > board, string word, int i, int j)， board为需要搜索的二维数组，word是目标字符串，i和j分别是起始元素所在的行和列index（从0开始编号）。递归算法在执行递归程序时，自动保存了两类信息：

1. 保存分岔口元素的地址，以便于返回到这个分岔路口；
2. 保存之前所选择的路口，以便于下一次进入另一个路口进行搜索。

所以，当我们使用dfs的非递归算法时，就需要手动来保存这两类信息。现在我们来看看dfs非递归版本的伪代码模板，但是下面的编码思路不会完全按照这个模板进行，会根据本题情况做适当改动：

递归模板

step 1

将栈初始化，同时也要将visitded访问标记数据初始化：

while (!s.empty())
    s.pop();
for (int i = 0; i < board.size(); i++) {
    fill(visited[i].begin(), visited[i].end(), false);
}

在本题中，还需要设立一个count变量int count = 0; ，表示目前已经搜索到word字符串的第几个字符。

step 2

访问起始顶点，在本题中，如果起始顶点和word字符串第一个字符对不上，那么可以直接返回falseif (board[i][j] != word[count]) return false;；如果起始顶点是word字符串的第一个字符，那么才将起始顶点改为“已访问”标志，将起始顶点进栈，此时还需要将count变量加一。

if (board[i][j] != word[count]) {
    return false;
} else {
    count++;
    visited[i][j] = true;
}

这里遇到了非递归算法的第一个问题：我该如何保存此元素地址。如果我在线性或非线性链表中进行搜索，入栈我只需要将此节点的地址入栈即可，但我现在是在二维数组中搜索，每个元素都由i和j两个坐标表示，难道我要一次入栈2个元素吗？这样也未尝不可，我也曾试过这个方法，每次入栈2个，出栈的时候也一次出2个元素。可是问题在于，我在只想访问栈顶元素而不要求出栈时，只能访问到一个坐标，另一个坐标需要出栈一个元素才能访问到。这就很麻烦了，真让人头大.jpg。

随后我又想到另一个方法，我可以按行顺序对每个元素进行排列，如果每行有10个元素，第一行就是0_{9，第二行便是10}19……以此类推。这样的话，我就可以使用一个数字表示出这个元素的坐标，需要用到i和j的时候，也可以很轻松的算出i和j，我可真是太机智了。

所以按此思路，入栈时应该是s.push(i * board[0].size() + j); 这条语句，i乘以每行元素个数再加上j，想访问栈顶元素时，便可以使用cur_i = s.top() / board[0].size();cur_j = s.top() % board[0].size();这两条语句。其中cur_i和cur_j是存储目前元素坐标的变量。

step 3

step 3.0

这是伪代码里没有写到的，此题不一定要遍历完全部的元素，只要搜索到目标字符串就可以返回true了，所以while循环体内要这样写：

while (!s.empty()) {   
    if (count == word.length())
        return true; 
    <code>
}

step 3.1

访问栈顶元素顶点，这里就可以使用上面提到的方法算出栈顶元素的地址了；

step 3.2

看看栈顶元素顶点存在未被访问过的邻接点w。这里又面临到非递归算法的第二个问题：如何记录这个顶点已经访问过哪些邻接点，还没有访问过哪些邻接点。因为已经访问过的点如果再访问一遍也是得到一样的结果，很容易陷入死循环。

对于这个问题，我想过好几个解决方案，最后我在代码中规定每个元素必须按照上下左右的顺序对周边元素进行访问，再使用一个辅助数组dircvector<vector<int> > dirc;来记录每个元素下一步可以对哪个周边元素进行访问，值可以为1、2、3、4，分别表示可以对上面元素、下面元素、左边元素、右边元素进行访问，若值为5，表示周边元素都访问完了，只能回退到上一个分岔路口，重做选择。我只需要判断dirc中的值，从而决定此元素下一步尝试向哪个方向走。

当我们决定向一个方向走的时候，我们还需要做3个判断：

1. 要确定这一步会不会造成数组越界。这里都已向上走为例，向上走时，需要判断cur_i - 1 >= 0；
2. 要确定下一个访问的元素是否已访问过，如果不判断的话，把路径走成一个环，然后陷入死循环出不来visited[cur_i - 1][cur_j] == false；
3. 需要判断下一个访问的元素是否与目标字符串里下一个元素相同board[cur_i - 1][cur_j] == word[count]。

如果通过了上面3个判断，就可以访问邻接点w了，并且将顶点w改为“已访问”标志visited[cur_i - 1][cur_j] = true;，再将顶点w入栈s.push((cur_i - 1) * board[0].size() + cur_j);，count变量也要加一count++;，意味着搜索下一个元素。

step 3.3

如果dirc中记录此元素四个方向都访问过了，那么只能回退，需要将此元素出栈s.pop();，访问标记置为“未访问”visited[cur_i][cur_j] = false;，dirc数组内的值重新置为1dirc[cur_i][cur_j] = 1;，count也要减一count--;。

完整代码：

class Solution {
public:
    stack<unsigned long> s;
    int a;
    vector<vector<bool>> visited;
    // dirc表示行走方向, 1：向上，2：向下，3：向左，4：向右，5：回退
    vector<vector<int>> dirc;
    
    void init (vector<vector<char> > &board) {
        visited.resize(board.size());
        dirc.resize(board.size());
        for (int i = 0; i < visited.size(); i++) {
            visited[i].resize(board[0].size());
            dirc[i].resize(board[0].size());
        }
        return;
    }
    
    bool DFSTraverse(vector<vector<char> > &board, string str, int i, int j){
        // 栈初始化
        while(!s.empty()) s.pop();
        // visited标记数组初始化
        for (int i = 0; i < board.size(); i++) {
            fill(visited[i].begin(), visited[i].end(), false);
            fill(dirc[i].begin(), dirc[i].end(), 1);
        }
        
        int count = 0;
        
        if (board[i][j] != str[count]) {
            return false;
        } else {
            count++;
            visited[i][j] = true;
            s.push(i * board[0].size() + j);
            int cur_i = i, cur_j = j;
          
            while (!s.empty()) {
                if (count == str.length()) return true;
                cur_i = s.top() / board[0].size();
                cur_j = s.top() % board[0].size();
                
                switch (dirc[cur_i][cur_j]) {            
                    case 1:
                        // 上
                        if (cur_i - 1 >= 0
                            && visited[cur_i - 1][cur_j] == false
                            && board[cur_i - 1][cur_j] == str[count]) {
                            visited[cur_i - 1][cur_j] = true;
                            s.push((cur_i - 1) * board[0].size() + cur_j);
                            count++;
                        }
                        dirc[cur_i][cur_j]++;
                        break;
                    case 2:
                        // 下
                        if (cur_i + 1 < board.size()
                            && visited[cur_i + 1][cur_j] == false
                            && board[cur_i + 1][cur_j] == str[count]) {
                            visited[cur_i + 1][cur_j] = true;
                            s.push((cur_i + 1) * board[0].size() + cur_j);
                            count++;
                        }
                        dirc[cur_i][cur_j]++;
                        break;
                    case 3:
                        // 左
                        if (cur_j - 1 >= 0
                            && visited[cur_i][cur_j - 1] == false
                            && board[cur_i][cur_j - 1] == str[count]) {
                            visited[cur_i][cur_j - 1] = true;
                            s.push(cur_i * board[0].size() + (cur_j - 1));
                            count++;
                        }
                        dirc[cur_i][cur_j]++;
                        break;
                    case 4:
                        // 右
                        if (cur_j + 1 < board[0].size()
                            && visited[cur_i][cur_j + 1] == false
                            && board[cur_i][cur_j + 1] == str[count]) {
                            visited[cur_i][cur_j + 1] = true;
                            s.push(cur_i * board[0].size() + (cur_j + 1));
                            count++;
                        }
                        dirc[cur_i][cur_j]++;
                        break;
                    case 5:
                        s.pop();
                        visited[cur_i][cur_j] = false;
                        dirc[cur_i][cur_j] = 1;
                        count--;
                        break;
                    default:
                        break;
                }
            }
            return false;
        }
    }
    
    bool exist(vector<vector<char> > &board, string word) {
        init(board);
        
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                if (DFSTraverse(board, word, i, j))
                    return true;
            }
        }
        
        return false;
    }
    
    bool test(vector<vector<char> > &board, string word) {
        init(board);
        return DFSTraverse(board, word, 1, 4) ? true : false;
    }
};