212. Word Search II:多个单词查找
寫在前面:這兩周持續看花花醬整理的題目列表和視頻講解,也得益于自己持續多年刷題,今天刷這道題目的想法是:會trie樹居然就能攻克hard題目!我也離獨立攻破hard題目不遠了嘛。前段時間看王爭在極客時間的系列課程,trie樹是不在話下的。好,開始寫題。
目錄
- 題目描述
- 暴力回溯
- Trie樹
題目描述
輸入:二維字符數組,做棋盤baord;字符串列表words。
返回:可以在棋盤中找到的所有單詞word。
規則:每個單詞需要按順序在棋盤中匹配,棋盤匹配的時候只能移動相鄰位置。相鄰位置是指上下左右。
例子:輸入
board = [
[‘o’,‘a’,‘a’,‘n’],
[‘e’,‘t’,‘a’,‘e’],
[‘i’,‘h’,‘k’,‘r’],
[‘i’,‘f’,‘l’,‘v’]
]
words = [“oath”,“pea”,“eat”,“rain”]
輸出: [“eat”,“oath”]
暴力回溯
按照回溯法,每次解決一個單詞word。可以參考題目79。
參考例子中,board的行列:m=4,n=4。查找單詞word=oath。dfs搜索的時候每找到單詞中的一個字符作為一層。在每一層向下一層移動過程中有上、下、左、右4種選擇。
枚舉每一個位置(i,j)作為起始查找位置。因為不確定哪個位置的ch與word的第一個字符相同。
dfs(i,j,index),i:第i行;j:第j列;index:單詞中的第index個字符。
如果 board[i][j]=word[index],則設置board[i][j]=’#’,防止重復查找,繼續向4個方向遍歷。
當index=word.length的時候,表示word是存在的,加入結果集。
當數組下標i,j越界,或者重復查找的時候返回。
如果board[i][j]!=word[index],則返回,不繼續搜索。
最終每個單詞查找一次,返回結果。
時間復雜度:$O(m?n?4l)O(m*n*4^l)O(m?n?4l),l=單詞長度
Trie樹
這里需要查找多個單詞。例如word=[“baa”,“bab”,“aaab”,“aaa”,“aaaa”]。單詞baa和bab有公共前綴ba,暴力回溯每次都從0開始查找,浪費時間。如果能查找到baa之后回溯一步,繼續查找到bab就好了。單詞aaa和aaaa,也是同樣的情況。這里就需要用到Trie樹。Trie樹在有公共前綴子串的情況下,會極大的降低時間復雜度。Trie樹學習可以參考我的博客。
上圖展示了構建完成的Trie樹結構。這里在每個單詞結束位置添加了word表示當前字符串的值。便于記錄結果。
和暴力回溯類似,遍歷每一個起始位置(i,j),從根節點開始查找。
dfs(i,j,node):每次查找到一個節點,word不為空,說明找到了一個字符串,加入結果集并且word設置為null。
數組下標i,j越界,或者重復訪問,則返回。
如果node.children[board[i][j]-‘a’]不為空,則繼續朝4個方向搜索。否則返回。
時間復雜度:構建trie樹的時間復雜度是所有單詞長度和:$O(sum(l))。
搜索過程,因為有合并搜索,所以最深的深度是max(l)。在每一層會查找4個方向,所以是O(4max(l))O(4^{max(l)})O(4max(l))
所以最終時間負責度是:O(sum(l)+4max(l))O(sum(l)+4^{max(l)})O(sum(l)+4max(l))
class Solution {private char[][] board;private String word;private int m;private int n;private TrieNode root;private List<String> result;public List<String> findWords(char[][] board, String[] words) {this.board = board;m = board.length;if(m == 0) return new ArrayList<String>();n = board[0].length;result = new ArrayList<String>();buildTree(words);for(int i=0;i<m;i++){for(int j=0;j<n;j++){dfs(i,j,root);}}return result;}private void dfs(int i,int j,TrieNode node){if(node.word!=null){result.add(node.word);node.word = null;}if(i<0 || i>=m || j<0 || j>=n || board[i][j]=='#'){return;} char ch = board[i][j];if(node.children[ch-'a']==null) return;TrieNode n = node.children[ch-'a'];board[i][j] = '#';dfs(i-1,j,n);dfs(i+1,j,n);dfs(i,j-1,n);dfs(i,j+1,n);board[i][j] = ch;}private void buildTree(String[] words){root = new TrieNode('/');for(String word : words){addWord(word);}}public void addWord(String word){TrieNode p = root;for(int i=0;i<word.length();i++){int idx = word.charAt(i)-'a';if(p.children[idx]==null){p.children[idx] = new TrieNode(word.charAt(i));}p = p.children[idx];}p.end = true;p.word = word;}class TrieNode{private char data;private boolean end;private TrieNode[] children = new TrieNode[26];private String word;public TrieNode(char data){this.data = data;}public boolean isEnd(){return end;}} }總結
以上是生活随笔為你收集整理的212. Word Search II:多个单词查找的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: PHP自动测试框架Top 10
- 下一篇: 某公司数据恢复报告书