LeetCode 212.单词搜索II

https://leetcode.cn/problems/word-search-ii/description/?envType=study-plan-v2&envId=top-interview-150

题目描述

给定一个 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 * 104
1 <= words[i].length <= 10
words[i] 由小写英文字母组成
words 中的所有字符串互不相同

解题思路

我们使用字典树把words中的所有单词存起来，同时为了便于查找子节点，我们的字典树实现的时候，可以把子节点的实现方式换位HashMap<Integer, String>这样可以实现快速查找，而且可以按需建立子节点

然后对我们的board进行dfs遍历，查找当前遍历的字符串是否在字典树中

• 剪枝：每当当前访问的节点不是字典树中的任意一个单词的前缀，剪掉
• 去重：同一个单词可能在多个不同的路径出现，所以使用哈希集合对结果去重。
• dfs遍历当前节点之前，可以修改当前节点为’#'， 遍历完在恢复
• 优化：删除匹配的单词，考虑以下情况。假设给定一个所有单元格都是 a 的二维字符网格和单词列表 [“a”, “aa”, “aaa”, “aaaa”] 。当我们使用方法一来找出所有同时在二维网格和单词列表中出现的单词时，我们需要遍历每一个单元格的所有路径，会找到大量重复的单词。

代码实现

class Solution {
    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};

    public List<String> findWords(char[][] board, String[] words) {
        Trie trie = new Trie();
        for(String word: words) {   // 插入字典树
            trie.insert(word);
        }

        Set<String> ans = new HashSet<String>();  // 结果集去重
        for(int i=0; i<board.length; i++){
            for(int j=0; j<board[0].length; j++){
                dfs(board, trie,i,j,ans);      // dfs
            }
        }

        return new ArrayList<String>(ans);
    }

    public void dfs(char[][] board, Trie now , int i1, int j1, Set<String> ans){
        if(!now.children.containsKey(board[i1][j1])){   // 剪枝
            return;
        }
        char ch = board[i1][j1];
        now = now.children.get(ch);
        if(!"".equals(now.word)){
            ans.add(now.word);
            now.word = "";     // 优化，这样省的去重
        }

        board[i1][j1] = '#';
        for(int[] dir: dirs){
            int i2 = i1 + dir[0];
            int j2 = j1 + dir[1];
            if(i2 >= 0 && i2 < board.length && j2 >= 0 && j2 < board[0].length){
                dfs(board, now, i2, j2, ans);
            }
        }
        board[i1][j1] = ch;
    }
}


class Trie{
    String word;
    Map<Character, Trie> children;    // 子节点实现方式换位hashMap
    // boolean isWord; // 这里暂时没用

    public Trie(){
        this.word = "";
        this.children = new HashMap<Character, Trie>();
    }

    public void insert(String word){
        Trie cur = this;
        for(int i=0; i< word.length(); i++){
            char c = word.charAt(i);
            if(!cur.children.containsKey(c)){
                cur.children.put(c, new Trie());
            }
            cur = cur.children.get(c);
        }
        cur.word = word;
    }
}