leetcode 79. Word Search

原题传送门—>

题目描述：
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.

示例

• 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.

标准的深搜题，直接上代码

class Solution {
public:
    int **mark;
    bool exist(vector<vector<char>>& board, string word) {
        if(board.empty())
            return false;
        mark = new int*[board.size()];
        for(int i = 0; i < board.size(); ++i)
        {
            mark[i] = new int[board[0].size()];
            memset(mark[i], 0, board[0].size()*4);
        }
        bool ans = false;
        for(int i = 0; i < board.size(); ++i)
        {
            for(int j = 0; j < board[0].size(); ++j)
            {
                   if(find(board, word, i, j, 0))
                {
                    for(int k = 0; k < board.size(); ++k)
                 {
                    delete []mark[k];
                 }
                     delete []mark; 
                       return true;
                }
            }
        }
            for(int k = 0; k < board.size(); ++k)
                 {
                    delete []mark[k];
                 }
                     delete []mark; 

        return false;
    }
    bool find(vector<vector<char>> & board, string & word,int row, int column, int pos)
    {
        if((row < 0)||(column < 0)||(row == board.size())||(column == board[0].size()))
            return false;
        if((mark[row][column])||(board[row][column] != word[pos]))
            return false;
        if(pos == word.size() - 1)
            return true;
        bool ans = false;
        mark[row][column] = 1;
            if(find(board, word, row - 1, column, pos + 1)||
               find(board, word, row, column - 1, pos + 1)||
               find(board, word, row + 1, column, pos + 1)||
               find(board, word, row, column + 1, pos + 1))
                return true;
        mark[row][column] = 0;
           return ans;
    }
};

不过这道题有一点需要注意：第47行之后这一段：

AC版本:

        bool ans = false;
        mark[row][column] = 1;
            if(find(board, word, row - 1, column, pos + 1)||
               find(board, word, row, column - 1, pos + 1)||
               find(board, word, row + 1, column, pos + 1)||
               find(board, word, row, column + 1, pos + 1))
                return true;
        mark[row][column] = 0;
           return ans;

原本我是这样写的，会超时：
TLE版本：

        bool ans = false;
        mark[row][column] = 1;
        ans |= find(board, word, row - 1, column, pos + 1);
        ans |= find(board, word, row, column - 1, pos + 1);
        ans |= find(board, word, row + 1, column, pos + 1);
        ans |= find(board, word, row, column + 1, pos + 1);
                return true;
        mark[row][column] = 0;
           return ans;

这两段代码我之前以为是一样的，但其实效率差很多，看TLE版本的代码：假如ans在第一步之后就变成true，那么之后的递归已经没有意义了，直接return就可以了。

而使用if判断时，对于||条件，当前一个条件值为1，便不会再执行之后的语句了，相当于直接return,所以效率要高很多。