LeetCode79: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.

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.

解题思路

双层 for 循环加上回溯法。这里边需要标记那个字母有没有被访问过,需要借助一个等大小的 boolean 二维数组。在递归之前进行标记,递归之后进行反标记。代码奉上

class Solution {
    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0) {
            return false;
        }
        if (word == null || word.length() == 0) {
            return false;
        }
        boolean[][] visted = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; ++i) {
            for (int j = 0; j < board[i].length; ++ j) {
                if (word.charAt(0) == board[i][j] && existHelper(board,  i, j, word, visted, 0)){
                    return true;
                }
            }
        }
        return false;

    }
    private boolean existHelper(char[][] board, int i, int j, String word, boolean[][] visted, int index) {

        if (i < 0 || i >= board.length || j < 0 || j >= board[i].length || board[i][j] != word.charAt(index) || visted[i][j]) {
            return false;
        }

        if (index == word.length() - 1) {
            return true;
        }
        visted[i][j] = true;
        if (existHelper(board, i- 1, j, word, visted, index + 1) ||
               existHelper(board, i + 1, j, word, visted, index + 1) ||
               existHelper(board, i, j - 1, word, visted, index + 1) ||
               existHelper(board, i, j + 1, word, visted, index + 1)) {
            return true;
        }
        visted[i][j] = false;
       return false;
    }
}

说点什么

avatar
  Subscribe  
提醒

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部