单词搜索
给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words，找出所有同时在二维网格和字典中出现的单词。
单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
示例 1：
输入：
board = [
["o","a","a","n"],
["e","t","a","e"],
["i","h","k","r"],
["i","f","l","v"]
],
words = ["oath","pea","eat","rain"]
输出：["eat","oath"]
示例 2：
输入：board = [
["a","b"],
["c","d"]
],
words = ["abcb"]
输出：[]
提示：
m == board.length
n == board[i].length
1 <= m, n <= 12
board[i][j] 是一个小写英文字母
1 <= words.length <= 3 * 10^4
1 <= words[i].length <= 10
words[i] 由小写英文字母组成
words 中的所有字符串互不相同
class Solution {
static int[][] d = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
static Map<String, Boolean> notExistWords = new HashMap<>();
public List<String> findWords(char[][] board, String[] words) {
List<String> ans = new ArrayList<>();
Arrays.sort(words);
notExistWords.clear();
for (int i = 0; i < words.length; i++) {
String word = words[i];
if (i > 0 && word.equals(words[i - 1]))
continue;
boolean notExistFlag = false;
for (int j = 1; j < word.length(); j++) {
if (notExistWords.containsKey(word.substring(0, j + 1))) {
notExistFlag = true;
break;
}
}
if (notExistFlag)
continue;
if (exist(board, word)) {
ans.add(word);
} else {
notExistWords.put(word, false);
}
}
return ans;
}
public boolean exist(char[][] board, String word) {
int m = board.length;
if (m == 0)
return false;
int n = board[0].length;
if (n == 0)
return false;
if (word.equals(""))
return true;
boolean[][] f = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (word.charAt(0) == board[i][j]) {
f[i][j] = true;
boolean flag = dfs(i, j, 1, board, word, m, n, f);
if (flag)
return true;
f[i][j] = false;
}
}
}
return false;
}
private boolean dfs(int i, int j, int k, char[][] board, String word, int m, int n, boolean[][] f) {
if (k == word.length()) {
return true;
}
for (int l = 0; l < 4; l++) {
if (i + d[l][0] < m && j + d[l][1] < n && i + d[l][0] >= 0 && j + d[l][1] >= 0
&& board[i + d[l][0]][j + d[l][1]] == word.charAt(k) && !f[i + d[l][0]][j + d[l][1]]) {
f[i + d[l][0]][j + d[l][1]] = true;
boolean flag = dfs(i + d[l][0], j + d[l][1], k + 1, board, word, m, n, f);
if (flag)
return true;
f[i + d[l][0]][j + d[l][1]] = false;
}
}
return false;
}
}