今天和大家聊的问题叫做 单词搜索 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']; } }
好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。
