电子商务网站建设 教材,长沙公司网站高端网站建设,怎么做网站的图片,济南住房和城乡建设厅网站写在前面#xff1a;这两周持续看花花酱整理的题目列表和视频讲解#xff0c;也得益于自己持续多年刷题#xff0c;今天刷这道题目的想法是#xff1a;会trie树居然就能攻克hard题目#xff01;我也离独立攻破hard题目不远了嘛。前段时间看王争在极客时间的系列课程#…写在前面这两周持续看花花酱整理的题目列表和视频讲解也得益于自己持续多年刷题今天刷这道题目的想法是会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的行列m4n4。查找单词wordoath。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个方向遍历。 当indexword.length的时候表示word是存在的加入结果集。 当数组下标ij越界或者重复查找的时候返回。 如果board[i][j]!word[index]则返回不继续搜索。
最终每个单词查找一次返回结果。 时间复杂度$O(m∗n∗4l)O(m*n*4^l)O(m∗n∗4l),l单词长度
class Solution {private char[][] board;private String word;private int m;private int n;public ListString findWords(char[][] board, String[] words) {this.board board;m board.length;if(m 0) return new ArrayListString();n board[0].length;ListString result new ArrayListString();for(String word : words){if(findWord(word)){result.add(word);}}return result;}private boolean findWord(String word) {this.word word;for(int i0;im;i){for(int j0;jn;j){if(dfs(i,j,0)){return true;}}}return false;}private boolean dfs(int i,int j,int index){if(index word.length()) return true;if(i0 || im || j0 || jn || board[i][j]#){return false;}boolean r false;if(board[i][j] word.charAt(index)){char ch board[i][j];board[i][j] #;r dfs(i-1,j,index1)|| dfs(i1,j,index1)|| dfs(i,j-1,index1)|| dfs(i,j1,index1);board[i][j] ch;}return r;}
}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 ListString result;public ListString findWords(char[][] board, String[] words) {this.board board;m board.length;if(m 0) return new ArrayListString();n board[0].length;result new ArrayListString();buildTree(words);for(int i0;im;i){for(int j0;jn;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(i0 || im || j0 || jn || 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(i1,j,n);dfs(i,j-1,n);dfs(i,j1,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 i0;iword.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;}}
}
