資訊專欄INFORMATION COLUMN
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 List findWords(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;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/72136.html
摘要：復(fù)雜度時間空間為長度，為大小空間復(fù)雜度是是因為我用存信息，只動態(tài)地存當(dāng)前的路徑如果用來存信息的話空間復(fù)雜度就是時間復(fù)雜度對每個點都要作為起始點，對于每個起始點，拓展一次有四個可能性四個鄰居，要拓展次長度為。思路暴力搜索帶走。 Word Search I Given a 2D board and a word, find if the word exists in the grid. ...
摘要：在線網(wǎng)站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...
摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經(jīng)到題，所以后面會調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。 一 目錄 不折騰的前端，和咸魚有什么區(qū)別...
摘要：我們可以先用待查單詞建立一個字典樹，這樣我們在從矩陣中某個點開始深度優(yōu)先搜索時，可以直接用字典樹判斷當(dāng)前組成的字符串是否是某個單詞的前綴。字典樹同樣也提供接口，所以同樣可以用于判斷是否已經(jīng)搜索到這個詞了。 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...
閱讀 2649·2021-11-23 09:51
閱讀 3413·2021-11-22 15:22
閱讀 1941·2021-11-18 13:22
閱讀 2395·2021-09-24 09:48
閱讀 1370·2019-08-29 13:58
閱讀 1369·2019-08-26 13:39
閱讀 2510·2019-08-26 10:48
閱讀 3104·2019-08-26 10:21
