[数据结构与算法]79. 单词搜索

一、题目描述

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

示例 2：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true

示例 3：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false

二、解题

回溯

这题主要是使用回溯算法，并且使用一个遍历数组visited记录访问过的位置，如果当前的board[i][j]!=word[index]，则直接放回false；否则，遍历当前位置的所有相邻位置。

class Solution {
    private final static int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    public boolean exist(char[][] board, String word) {
        //这题使用回溯 而且使用一个额外的visited数组
        int m = board.length,n = board[0].length;
        boolean[][] visited = new boolean[m][n];
        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                if(dfs(board,word,0,i,j,visited)){
                    return true;
                }
            }
        }
        return false;
    }
    public boolean dfs(char[][] board, String word, int index, int i, int j, boolean[][] visited){
        //跳出条件 判断当前的索引值是否到达字符的长度        
        if(board[i][j] != word.charAt(index)){
            return false;
        }else if(index == word.length()-1){
            return true;            
        }
        //若当前索引值为字符串的值
        //将遍历数组设置为true 表示访问过
        visited[i][j] = true;
        for(int[] dir : direction){
            if(i+dir[0]>=0 && i+dir[0]<board.length && j+dir[1]>=0 && j+dir[1]<board[0].length){
                //看新的坐标是否被访问过
                if(!visited[i+dir[0]][j+dir[1]]){
                    //如果下一个位置返回正确 遍历到 就返回true
                    if(dfs(board,word,index+1,i+dir[0],j+dir[1],visited)){
                        return true;
                    } 
                }
            }
        }
        visited[i][j] = false;
        return false;
    }
}