单词搜索

2020-09-13

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

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

示例:

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

给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false


提示：

board 和 word 中只包含大写和小写英文字母。
1 <= board.length <= 200
1 <= board[i].length <= 200
1 <= word.length <= 10^3

主要思路
本题本质上还是回溯算法的运用，啊啊啊啊，回溯好难啊，今天的卡点在于怎么正确的在回溯过程中设置返回值，有进步的在于整体思路还是没得问题，重点在于返回值的确定，多刷题，多看吧
技巧：利用二维偏移量数组来简化代码

class Solution {
    public boolean exist(char[][] board, String word) {
        if(board.length==0)
			return false;
		int l = board.length;
		int w = board[0].length;
		boolean [][] visited = new  boolean[l][w];
		for(int i = 0;i<l;i++) {
			for(int j = 0;j<w;j++) {
				if(board[i][j]==word.charAt(0)) {
					if(dfs(board, visited, i, j, word, 0))
						return true;
					
				}
			}
		}
		return false;
    }
    public static boolean dfs(char [][] board,boolean [][] visited,int i,int j,String word,int index) {
		if(index==word.length()-1)
			return board[i][j]==word.charAt(index);
        if(board[i][j]!=word.charAt(index))
			return false;
		visited[i][j] = true;
		int [][] directions = {{0,1},{0,-1},{1,0},{-1,0}};
		for(int[]com:directions) {
			int newX = i+com[0];
			int newY = j+com[1];
			if(newX>=0&&newX<board.length&&newY>=0&&newY<board[0].length&&visited[newX][newY]==false)
				if(dfs(board, visited, newX, newY, word, index+1)) {
					return true;
				}
		}
		visited[i][j] = false;
		return false;
}
}