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;}
}