基础数据结构(一) -- Trie

[@henryjiang4808]

老师为了利用Trie结构，调用了startWith和search方法，在进行DFS时候浪费大量时间做重复检查导致TLE。 解决方法很简单，在DFS里自己写search方法，看是否reach the word，true->add in set, false-> return. 感谢古城的教程，很好！

[@維仁陳-c2k]

這邊提供Word Search II 一個AC答案，原本的解法在新的test cases會TLE。 在新的test case中，如果用迷宮組成String再去trie裡面搜索，會造成TLE。因為迷宮中每走一步，我們都是重頭在trie中搜索，比如說當前的String是app，下一步走到s，我們在trie中又會從a開始去比較，然後比p，再來比較p，最後比較剛剛走的那步的char，即是s。但是app這幾個character在上一步就已經比較過了，其實不需要每次都重頭比較。 How to improve? 我們只需要比較剛剛走的那步的char，然後看看有沒有對應的下一層trie node，所以把trie node傳入參數。 注意: 這樣我們就不需要trie的search和searchPrefix的method了。 程式碼: class Solution { Trie trie = new Trie(); int m = 0; // number of rows int n = 0; // number of columns List ans; // store final answer boolean[][] visit; // indicates whether current cell is visited int[][] directions; // 上下左右 public List findWords(char[][] board, String[] words) { for(String s: words){ trie.addWord(s); } m = board.length; n = board[0].length; ans = new ArrayList(); visit = new boolean[m][n]; directions = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ visit[i][j] = true; dfs(board, i, j, trie.root); visit[i][j] = false; } } return ans; } public void dfs(char[][] board, int row, int col, TrieNode node){ char c = board[row][col]; // 如果下一層沒有對應的trie node if(node.children[c - 'a'] == null){ return; } // 走到下一層 node = node.children[c - 'a']; // 這裡在trieNode加了一個field，見下面trieNode addWord的實現 if(node.isWord){ // 避免添加重複元素 if(!ans.contains(node.s)) ans.add(node.s); } // 往上往下往左往右走 for(int[] dir: directions){ int newRow = row + dir[0]; int newCol = col + dir[1]; if(newRow < 0 || newRow == m || newCol < 0 || newCol == n) continue; if(visit[newRow][newCol]) continue; visit[newRow][newCol] = true; dfs(board, newRow, newCol, node); visit[newRow][newCol] = false; } } } class Trie{ TrieNode root; public Trie(){ root = new TrieNode(); } public void addWord(String s){ TrieNode node = root; for(char c: s.toCharArray()){ if(node.children[c - 'a'] == null) node.children[c - 'a'] = new TrieNode(); node = node.children[c - 'a']; } node.s = s; node.isWord = true; } } class TrieNode{ TrieNode[] children; boolean isWord; String s; public TrieNode(){ children = new TrieNode[26]; } }

[@zzz9745]

讲的很棒！ 不过Word Search II 这题现在这样写会TLE了，得加个removeWord操作才能过了

[@weiyao806]

非常受益，讲得很棒，尤其是bitwise字典树，这个想法真是绝了。

[@古城算法]

谢谢支持！！哈哈😆

[@ningshen5371]

您的课真的非常好。希望以后还能有OOD, System Design 的课

[@古城算法]

谢谢鼓励，我也会继续努力！

[@古城算法]

SD我有点经验不太够啊哈哈哈，不过可以照葫芦画瓢搞搞基础入门的。

[@superheroherohero]

你好大神，现在（July 27, 2022) 212. Word Search II 题的解法好像超时了，有更新的解法吗？ 多谢！

[@baoyuan3955]

讲得很好 就是视频可不可以1080p啊哈哈哈哈

[@古城算法]

哈哈哈，谢谢，前期设备还不齐全，后面就都换1440p了

[@eaglezhou1243]

@古老师，您的课讲的太好了，真看不出你还是中途转行的，牛逼。 我已经发出加群请求了， 求拉进去， 多多谢。

[@古城算法]

感谢支持！我来拉你！

[@eaglezhou1243]

@@古城算法 已经被拉进去了，谢谢

[@StevenWang-x7u]

求加群。

[@dexw4]

请问可以也加入群吗，感谢！

[@joepeng5136]

古城大神讲的很清晰！感谢！

[@wryanchow8030]

讲得好好呀 感谢城主！

[@songrencheng8665]

古城喜欢打pubg，有机会一块呀

[@古城算法]

哈哈，那是很早很早以前啦，现在玩原神了。

[@songrencheng8665]

@@古城算法 😭

[@chrisgu4121]

感谢！非常受益！