79. Word Search

Leetcode Array Backtracking

题目

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.

分析

这道题目和迷宫非常相似。Word类似于迷宫的出路。Board类似于迷宫。区别就是没有了迷宫的出发点和出路的数目是固定的。所以一开始就构造一系列出发点，变动word使其达到base case。还有一个区别就是路不能重复走，所以走动以后可以改为'.'，使其不匹配。

class Solution {
public:

    bool exist_helper(vector<vector<char>>& board, int& nrow, int& ncolumn, string& word,  int row, int column){
        if (!word.size()){
            //base case
            return true;
        } if(row<0||column<0||column>ncolumn-1||row>nrow-1){
            // 出了边界，无效
            return false;
        } else if (board[row][column]==word[0]){            
            //choose and explore
            word.erase(word.begin());
            char s = board[row][column];
            board[row][column]= '.';
            bool result = exist_helper(board, nrow, ncolumn, word, row+1, column)
                    || exist_helper(board, nrow, ncolumn,  word, row-1, column)
                    || exist_helper(board, nrow, ncolumn,  word, row, column+1)
                    || exist_helper(board, nrow, ncolumn, word, row, column-1);
            //unchoose
            if (!result){
                word.insert(word.begin(), s);
                board[row][column] = s;
            }
            return result;
        } else{
            return false;
        }
    }

    bool exist(vector<vector<char>>& board, string word) {

        int nrow = board.size();
        int ncolumn = board[0].size();
        bool res = false;

        //构造迷宫出发点
        for (int i=0; i<nrow; i++){
            for (int j=0; j<ncolumn; j++){
                res = res | exist_helper(board, nrow, ncolumn, word, i, j);
            }
        }

        return res;
    }
};