212. Word Search II

题目描述和难度

  • 题目描述：

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

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

示例:

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

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

说明:
你可以假设所有输入都由小写字母 a-z 组成。

提示:

  • 你需要优化回溯算法以通过更大数据量的测试。你能否早点停止回溯？
  • 如果当前单词不存在于所有单词的前缀中，则可以立即停止回溯。什么样的数据结构可以有效地执行这样的操作？散列表是否可行？为什么？ 前缀树如何？如果你想学习如何实现一个基本的前缀树，请先查看这个问题： 实现Trie（前缀树）。

思路分析

求解关键：使用字典树 + 搜索的方法可以完成。

  • 字典树的结点要暴露出来。

参考解答

参考解答1

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Solution {

    // 参考资料：
    // https://leetcode.com/problems/word-search-ii/discuss/148041/Clean-Java-Code-Trie

    //         x-1, y
    // x, y-1  x, y    x, y+1
    //         x+1,y
    private static final int[][] directions = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};

    private class TrieNode {
        private TrieNode[] next;
        private boolean isEnd;
        private String word;

        public TrieNode() {
            next = new TrieNode[26];
            isEnd = false;
        }
    }

    public List<String> findWords(char[][] board, String[] words) {
        List<String> res = new ArrayList<>();
        if (words == null || words.length == 0) {
            return res;
        }
        int row = board.length;
        if (row == 0) {
            return res;
        }
        int col = board[0].length;
        TrieNode root = new TrieNode();
        boolean[][] visited = new boolean[row][col];
        for (String word : words) {
            TrieNode curNode = root;
            for (char c : word.toCharArray()) {
                if (curNode.next[c - 'a'] == null) {
                    curNode.next[c - 'a'] = new TrieNode();
                }
                curNode = curNode.next[c - 'a'];
            }
            if (!curNode.isEnd) {
                curNode.isEnd = true;
                curNode.word = word;
            }
        }

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                dfs(board, visited, i, j, row, col, root, res);
            }
        }
        // 最后要去重
        Set<String> set = new HashSet(res);
        res = new ArrayList<>(set);
        return res;
    }

    /**
     * @param board   字符面板
     * @param visited 记录当前坐标是否被访问过
     * @param i       横坐标
     * @param j       纵坐标
     * @param row     横坐标的最大值
     * @param col     纵坐标的最大值
     * @param node    当前字典树结点
     * @param res     结果集
     */
    private void dfs(char[][] board, boolean[][] visited, int i, int j, int row, int col, TrieNode node, List<String> res) {
        if (node.isEnd) {
            res.add(node.word);
        }
        if (inArea(i, j, row, col) && !visited[i][j]) {
            TrieNode nextNode = node.next[board[i][j] - 'a'];
            // 特别注意这个访问的位置
            visited[i][j] = true;
            if (nextNode != null) {
                for (int k = 0; k < 4; k++) {
                    int newX = i + directions[k][0];
                    int newY = j + directions[k][1];
                    dfs(board, visited, newX, newY, row, col, nextNode, res);
                }
            }
            // 特别注意这个访问的位置
            visited[i][j] = false;
        }
    }

    private boolean inArea(int i, int j, int row, int col) {
        return i >= 0 && i < row && j >= 0 && j < col;
    }

    public static void main(String[] args) {
        String[] words = {"oath", "pea", "eat", "rain"};
        char[][] board = {
                {'o', 'a', 'a', 'n'},
                {'e', 't', 'a', 'e'},
                {'i', 'h', 'k', 'r'},
                {'i', 'f', 'l', 'v'}};
        Solution solution = new Solution();
        List<String> solutionWords = solution.findWords(board, words);
        System.out.println(solutionWords);
    }
}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0212-word-search-ii ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。