79WordSearch.org

[#B] 79 Word Search - LeetCode

题目

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.

思路

通过回溯法+深度遍历，对满足条件的位置进行上下左右深度遍历

Java

class Solution {
 
    int[][] d = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    boolean[][] visted;
 
    public boolean exist(char[][] board, String word) {
        visted = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (searchWord(board, word, 0, i, j)) {
                    return true;
                }
            }
        }
        return false;
    }
 
    public boolean searchWord(char[][] board, String word, int index, int startx, int starty) {
        if (index == word.length() - 1) {
            return board[startx][starty] == word.charAt(index);
        }
     
        if (board[startx][starty] == word.charAt(index)) {
            visted[startx][starty] = true;
            for (int i = 0; i < 4; i++) {
                int newX = startx + d[i][0];
                int newY = starty + d[i][1];
             
                if (inArea(board, newX, newY) && !visted[newX][newY] && searchWord(board, word, index + 1, newX,newY)){
                    return true;
                }
            }
            visted[startx][starty] = false;
        }
        return false;
    }
    public boolean inArea(char[][] board, int x, int y) {
        return x >= 0 && x < board.length && y >= 0 && y < board[0].length;
    }
}

CPP

class Solution {
public:
    int d[4][2] = {{-1,0}, {0, -1}, {1, 0}, {0, 1}};
    int m,n;
    vector<vector<bool>> visted;
 
    bool exist(vector<vector<char>>& board, string word) {
        m = board.size();
        if (m <= 0) return false;
        n = board[0].size();
        visted = vector<vector<bool>>(m, vector<bool>(n, false));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (searchWord(board, word, 0, i, j)){
                    return true;
                }
            }
        }
        return false;
    }
 
    bool searchWord(vector<vector<char>>& board, string word, int index, int startx, int starty) {
        if (index == word.size() - 1)
            return board[startx][starty] == word[index];
     
        if (board[startx][starty] == word[index]) {
            visted[startx][starty] = true;
            for (int i = 0; i < 4; i++) {
                int newX = startx + d[i][0];
                int newY = starty + d[i][1];
                if (inArea(newX, newY) && !visted[newX][newY] && searchWord(board, word, index + 1, newX, newY)) {
                    return true;
                }
            }
            visted[startx][starty] = false;
        }
        return false;
    }
 
    bool inArea(int x, int y) {
        return x >= 0 && x < m && y >=0 && y < n;
    }
};