79. Word Search

problem description

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.

algorithm thought

思路很简单，都类似一种暴力搜索法，直接从每个节点都开始搜索，如果是当前节点是对的，就从这个节点的4个方向继续搜索。使用DFS搜索，每一层都有4个分量。唯一需要注意的就是不能搜索到重复的值，也就是我这里搜索完，我去我右边的节点，我右边的节点不能再搜索这个原来的节点了。

有一种方法就是用标志，显示这里已经被搜索了，每次搜索完之后将当前字符设置为0。那么之后肯的和他匹配不了了。

还有一种思路利用异或的特性。异或两次回到原值，那么我们经历一个节点之后只需要将这个节点异或一下，之后回来的时候再异或一下，就能恢复。这种好处是可以不用中间变量来保存中间值，但是坏处就是异或之后的值可能会对之后的程序产生影响，我当时就是用这种思路，结果到倒数第二个样例的时候，失败了。最后换了第一种方法

update 2019/10/16 :

下午上课忽然想通了中午异或的问题，我中午出问题的代码是board[i][j]^=1.大家应该都知道，char是1个字节的，有8位，但是数字1是0000001，所以异或之后只有最后一位会改变。只改变最后一位的话，很容易导致异或之后和其他字符相同。

所以想通之后，直接将代码改为board[i][j]^=255就稳稳的过了。（255=11111111）

code

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        for(int i=0;i<board.size();i++){
            for(int j=0;j<board[0].size();j++){
                if(help(board,word,i,j,0))
                    return true;
            }
        }
        return false;
    }
    bool help(vector<vector<char>>&board, string&word,int i,int j,int pos){
        if(pos==word.size())
            return true;
        
        if(i<0||j<0||i>=board.size()||j>=board[0].size()||board[i][j]=='\0'||word[pos]!=board[i][j])
            return false;
        
        char t=board[i][j];
        board[i][j]='\0';
        if(
        help(board,word,i+1,j,pos+1)||
        help(board,word,i,j+1,pos+1)||
        help(board,word,i-1,j,pos+1)||
        help(board,word,i,j-1,pos+1)
        ){
            board[i][j]=t;
            return true;
        }
        board[i][j]=t;
        return false;
    }
};


class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        for(int i=0;i<board.size();i++){
            for(int j=0;j<board[0].size();j++){
                if(help(board,word,i,j,0))
                    return true;
            }
        }
        return false;
    }
    bool help(vector<vector<char>>&board, string&word,int i,int j,int pos){
        if(pos==word.size())
            return true;
        
        if(i<0||j<0||i>=board.size()||j>=board[0].size()||word[pos]!=board[i][j])
            return false;
        
        board[i][j]^=255;
        //board[i][j]='\0';
        if(
        help(board,word,i+1,j,pos+1)||
        help(board,word,i,j+1,pos+1)||
        help(board,word,i-1,j,pos+1)||
        help(board,word,i,j-1,pos+1)
        ){
            board[i][j]^=255;
            return true;
        }
        board[i][j]^=255;
        return false;
    }
};

algorithm analysis

DFS，每层有4个分量，时间复杂度还是挺高的，但是不好分析。我这里就不分析了