Problem
Given a 2D board and a list of words from the dictionary, find all words in the board.
Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.
Example:
Input: words = ["oath","pea","eat","rain"] and board = [ ["o","a","a","n"], ["e","t","a","e"], ["i","h","k","r"], ["i","f","l","v"] ] Output: ["eat","oath"]
Note:
You may assume that all inputs are consist of lowercase letters a-z.
class Solution { class TrieNode { TrieNode[] children = new TrieNode[26]; String word; } private TrieNode buildTrie(String[] words) { TrieNode root = new TrieNode(); for (String word: words) { TrieNode cur = root; for (char ch: word.toCharArray()) { int i = ch-"a"; if (cur.children[i] == null) cur.children[i] = new TrieNode(); cur = cur.children[i]; } cur.word = word; } return root; } public ListfindWords(char[][] board, String[] words) { List res = new ArrayList<>(); TrieNode root = buildTrie(words); for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[0].length; j++) { dfs(board, i, j, root, res); } } return res; } private void dfs(char[][] board, int i, int j, TrieNode root, List res) { char ch = board[i][j]; if (ch == "#" || root.children[ch-"a"] == null) return; root = root.children[ch-"a"]; if (root.word != null) { //found one res.add(root.word); root.word = null; //de-dup } board[i][j] = "#"; if (i > 0) dfs(board, i-1, j, root, res); if (j > 0) dfs(board, i, j-1, root, res); if (i < board.length-1) dfs(board, i+1, j, root, res); if (j < board[0].length-1) dfs(board, i, j+1, root, res); board[i][j] = ch; } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/72136.html
摘要:复杂度时间空间为长度,为大小空间复杂度是是因为我用存信息,只动态地存当前的路径如果用来存信息的话空间复杂度就是时间复杂度对每个点都要作为起始点,对于每个起始点,拓展一次有四个可能性四个邻居,要拓展次长度为。思路暴力搜索带走。 Word Search I Given a 2D board and a word, find if the word exists in the grid. ...
摘要:在线网站地址我的微信公众号完整题目列表从年月日起,每天更新一题,顺序从易到难,目前已更新个题。这是项目地址欢迎一起交流学习。 这篇文章记录我练习的 LeetCode 题目,语言 JavaScript。 在线网站:https://cattle.w3fun.com GitHub 地址:https://github.com/swpuLeo/ca...我的微信公众号: showImg(htt...
摘要:月下半旬攻略道题,目前已攻略题。目前简单难度攻略已经到题,所以后面会调整自己,在刷算法与数据结构的同时,攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题,目前已攻略 100 题。 一 目录 不折腾的前端,和咸鱼有什么区别...
摘要:我们可以先用待查单词建立一个字典树,这样我们在从矩阵中某个点开始深度优先搜索时,可以直接用字典树判断当前组成的字符串是否是某个单词的前缀。字典树同样也提供接口,所以同样可以用于判断是否已经搜索到这个词了。 Word Search I 更新的思路与解法请访问:https://yanjia.me/zh/2018/11/... Given a 2D board and a word, f...
摘要:自己没事刷的一些的题目,若有更好的解法,希望能够一起探讨项目地址 自己没事刷的一些LeetCode的题目,若有更好的解法,希望能够一起探讨 Number Problem Solution Difficulty 204 Count Primes JavaScript Easy 202 Happy Number JavaScript Easy 190 Reverse Bi...
阅读 2526·2021-11-23 09:51
阅读 3332·2021-11-22 15:22
阅读 1849·2021-11-18 13:22
阅读 2177·2021-09-24 09:48
阅读 1282·2019-08-29 13:58
阅读 1273·2019-08-26 13:39
阅读 2394·2019-08-26 10:48
阅读 3015·2019-08-26 10:21