有没有可以做翻译的网站吗,无忧建站,企业信息系统开发,自己做网站投放广告https://leetcode.cn/problems/word-search-ii/description/?envTypestudy-plan-v2envIdtop-interview-150 文章目录 题目描述解题思路代码实现 题目描述
给定一个 m x n 二维字符网格 board 和一个单词#xff08;字符串#xff09;列表 words#xff0c; 返回所有二…https://leetcode.cn/problems/word-search-ii/description/?envTypestudy-plan-v2envIdtop-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中的所有单词存起来同时为了便于查找子节点我们的字典树实现的时候可以把子节点的实现方式换位HashMapInteger, String这样可以实现快速查找而且可以按需建立子节点
然后对我们的board进行dfs遍历查找当前遍历的字符串是否在字典树中
剪枝每当当前访问的节点不是字典树中的任意一个单词的前缀剪掉去重同一个单词可能在多个不同的路径出现所以使用哈希集合对结果去重。dfs遍历当前节点之前可以修改当前节点为’# 遍历完在恢复优化删除匹配的单词考虑以下情况。假设给定一个所有单元格都是 a 的二维字符网格和单词列表 [“a”, “aa”, “aaa”, “aaaa”] 。当我们使用方法一来找出所有同时在二维网格和单词列表中出现的单词时我们需要遍历每一个单元格的所有路径会找到大量重复的单词。
代码实现
class Solution {int[][] dirs {{1,0},{-1,0},{0,1},{0,-1}};public ListString findWords(char[][] board, String[] words) {Trie trie new Trie();for(String word: words) { // 插入字典树trie.insert(word);}SetString ans new HashSetString(); // 结果集去重for(int i0; iboard.length; i){for(int j0; jboard[0].length; j){dfs(board, trie,i,j,ans); // dfs}}return new ArrayListString(ans);}public void dfs(char[][] board, Trie now , int i1, int j1, SetString 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;MapCharacter, Trie children; // 子节点实现方式换位hashMap// boolean isWord; // 这里暂时没用public Trie(){this.word ;this.children new HashMapCharacter, Trie();}public void insert(String word){Trie cur this;for(int i0; 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;}
}
