1号店网站网页特效,网站快速建设视频,网页制作和网站制作有什么区别,打开百度大致思路是#xff1a;
根据words列表建立字典树#xff0c;其中注意在单词末尾#xff0c;将原来的isEnd变量换成存储这个单词的变量#xff0c;方便存储到ans中#xff0c;另外#xff0c;字典树的字节点由原来的Trie数组变为hashmap#xff0c;方便检索字母。
建立…大致思路是
根据words列表建立字典树其中注意在单词末尾将原来的isEnd变量换成存储这个单词的变量方便存储到ans中另外字典树的字节点由原来的Trie数组变为hashmap方便检索字母。
建立完字典树后以board的每一个位置的字母为开头开始检索如果能检索到某一个Trie节点的word属性不为空字符串那么就是检索到了对应单词将其存储在ans中。
检索方式为深度优先搜索并对每个节点的上下左右的4个相邻节点进行进一步的深度优先搜索这里要注意不要超出board边界。
另外ans的类型要设置为set类型因为会存在前缀相同的情况。 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);}// ListString ans new ArrayList();SetString ans new HashSet(); // 注意ans的类型for (int i 0; i board.length; i) {for (int j 0; j board[0].length; j) {dfs(board, i, j, trie, ans);}}return new ArrayListString(ans);}private void dfs(char[][] board, int i, int j, Trie node, SetString ans) {if (!node.children.containsKey(board[i][j])) return;char ch board[i][j];node node.children.get(ch);if (node.word ! ) ans.add(node.word);board[i][j] #; // 标记已访问for (int[] dir : dirs) {int i2 i dir[0], j2 j dir[1];if (i2 0 i2 board.length j2 0 j2 board[0].length){dfs(board, i2, j2, node, ans); }}board[i][j] ch; // 回溯到原来字符因为正常是使用visited来标记已访问的元素的}
}class Trie {public String word;public MapCharacter, Trie children;// boolean isWord;public Trie() {this.word ;this.children new HashMap();}public void insert(String word) {Trie node this;for (int i 0; i word.length(); i) {char c word.charAt(i);if (!node.children.containsKey(c)) {node.children.put(c, new Trie());}node node.children.get(c);}node.word word;}
}
