「力扣」第 212 题：单词搜索 II（困难）

• 题目链接：212. 单词搜索 II (opens new window)。

题目描述

给定一个 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 中的所有字符串互不相同

参考代码：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution {

    private static final int[][] DIRECTIONS = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
    private int rows;
    private int cols;

    private boolean[][] visited;

    private class TrieNode {
        private Map<Character, TrieNode> next = new HashMap<>();
        private String isWord;
    }


    public List<String> findWords(char[][] board, String[] words) {
        // 第 1 步：构建前缀树
        TrieNode root = new TrieNode();
        for (String word : words) {
            TrieNode currNode = root;
            char[] charArray = word.toCharArray();
            for (Character c : charArray) {
                if (!currNode.next.containsKey(c)) {
                    currNode.next.put(c, new TrieNode());
                }
                currNode = currNode.next.get(c);
            }
            currNode.isWord = word;
        }


        // 第 2 步： 回溯算法找所有匹配的单词
        this.rows = board.length;
        this.cols = board[0].length;
        this.visited = new boolean[rows][cols];
        List<String> res = new ArrayList<>();

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (root.next.containsKey(board[i][j])) {
                    dfs(board, i, j, root, visited, res);
                }
            }
        }
        return res;
    }

    private void dfs(char[][] board, int i, int j, TrieNode currNode, boolean[][] visited, List<String> res) {
        Character letter = board[i][j];
        TrieNode nextNode = currNode.next.get(letter);

        if (nextNode.isWord != null) {
            res.add(nextNode.isWord);
            // 找到了就从字典中删除
            nextNode.isWord = null;
            // 思考这里为什么不可以 return

        }

        visited[i][j] = true;
        for (int[] direction : DIRECTIONS) {
            int newX = i + direction[0];
            int newY = j + direction[1];
            if (inArea(newX, newY) && !visited[newX][newY] && nextNode.next.containsKey(board[newX][newY])) {
                dfs(board, newX, newY, nextNode, visited, res);
            }
        }
        visited[i][j] = false;

        // 理解下面的代码非常重要
        // 优化：增量删除叶节点，Optimization: incrementally remove the leaf nodes
        if (nextNode.next.isEmpty()) {
            currNode.next.remove(letter);
        }
    }

    private boolean inArea(int x, int y) {
        return x >= 0 && x < rows && y >= 0 && y < cols;
    }
}

---

作者：liweiwei1419 链接：https://suanfa8.com/trie/solutions/0212.word-search-ii 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。