LeetCode刷题实战212：单词搜索 II / 开普饭

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 单词搜索 II，我们先来看题面：

https://leetcode-cn.com/problems/word-search-ii/

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

题意

给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words，找出所有同时在二维网格和字典中出现的单词。

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

示例

输入：board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]

输出：["eat","oath"]

提示：

m == board.length
n == board[i].length
1 <= m, n <= 12
board[i][j] 是一个小写英文字母
1 <= words.length <= 3 * 104
1 <= words[i].length <= 10
words[i] 由小写英文字母组成
words 中的所有字符串互不相同

解题

方法：前缀树+深度优先搜索。

public class Solution {
private TrieNode root = new TrieNode();
private int[] ro = {-1, 1, 0, 0};
private int[] co = {0, 0, -1, 1};
private void find(char[][] board, boolean[][] visited, int row, int col, TrieNode node, Set<String> founded) {
  visited[row][col] = true;
  TrieNode current = node.nexts[board[row][col]-'a'];
  if (current.word != null) founded.add(current.word);
  for(int i=0; i<4; i++) {
   int nr = row + ro[i];
   int nc = col + co[i];
   if (nr < 0 || nr >= board.length || nc < 0 || nc >= board[nr].length || visited[nr][nc]) continue;
   TrieNode next = current.nexts[board[nr][nc]-'a'];
   if (next != null) find(board, visited, nr, nc, current, founded);
  }
  visited[row][col] = false;
}
public List<String> findWords(char[][] board, String[] words) {
  Set<String> founded = new HashSet<>();
  for(int i=0; i<words.length; i++) {
   char[] wa = words[i].toCharArray();
   TrieNode node = root;
   for(int j=0; j<wa.length; j++) node = node.append(wa[j]);
   node.word = words[i];
  }
  boolean[][] visited = 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 (root.nexts[board[i][j]-'a'] != null) find(board, visited, i, j, root, founded);
   }
  }
  List<String> results = new ArrayList<>();
  results.addAll(founded);
  return results;
}
}
class TrieNode {
String word;
TrieNode[] nexts = new TrieNode[26];
TrieNode append(char ch) {
  if (nexts[ch-'a'] != null) return nexts[ch-'a'];
  nexts[ch-'a'] = new TrieNode();
  return nexts[ch-'a'];
}
}