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.

For example,
Given board =

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

word =”ABCCED” return true;

word= “SEE return true;

word=”ABCB” return false;

大意

从一个位置走到另一个位置，看能不能拼成给定的字符串，走过的不能重复。

答案

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int h = board.size();
        if(h==0) return false;
        int w = board[0].size();
        if(w==0) return false;
        int l = word.size();
        if(l==0) return false;
        vector<vector<bool>> visited(h, vector<bool>(w, false));
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                if(dfs(board, word, visited, 0, i, j)) return true;
            }
        }
        return false;
    }
    //idx 记录遍历到第几个单词了。,i j记录遍历的位置。
    bool dfs(vector<vector<char>>& board, string& word, vector<vector<bool>>& visited, int idx, int i, int j){
        if(idx == word.size()) return true;
        if(i<0 || j<0 || i>=board.size() || j>=board[0].size() || visited[i][j] || board[i][j] != word[idx]) return false;
        visited[i][j] = true;
        if(dfs(board, word, visited, idx+1, i, j+1)) return true;
        if(dfs(board, word, visited, idx+1, i, j-1)) return true;
        if(dfs(board, word, visited, idx+1, i+1, j)) return true;
        if(dfs(board, word, visited, idx+1, i-1, j)) return true;
        visited[i][j] = false;
        return false;
    }
};

思路

使用深度优先搜索，同时再使用相同大小的visited用来标记是否访问过。