本文主要是介绍Leetcode. 212 单词搜索II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目信息
LeetoCode地址: 力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
题目理解
该题目也是匹配字符串,但是高级一点。首先,要找到的字符串不再是单一一个,而是一个列表words,最大有3 *10^4个。其次,我们要在一个二维字符网格board上找寻,不再是若干个单词,即一个一维的字符数组。有点像需要棋盘上从任何一个位置开始走出一条蛇形路径,该路径刚好匹配字符串word。而每一步该怎么走呢?有四个方向,当然就有四个走法,到下一个位置后,同样有四种走法。那终止条件是什么?撞墙或者是四个方向的位置都已经用过了!所以我们每走一步,都要标记该位置以免走重复。而在该位置探索完返回时,要将标记抹除,就像一条蛇沿原路返回回退一样。简单地说,就是DFS+回溯。
写法1
我在刚开始思考这道题时,希望能够将board上的每一种可能路径都包含在Trie树中。在dfs过程中,由于words中每个字符串长度不超过10,所以dfs的深度也可以控制在10层以内。
其次,对于products每个字符串首字母没出现过的字符,都可以在遍历board每一个字符时过滤掉,无需进行dfs。
在构建好trie树后,再依次对words中的每一个元素进行遍历搜索,命中的元素加入到最终结果集中。
在board 为 m*n 大小,words 长度为p,每个字符串平均长度为q的情况下
时间复杂度: O(max(m*n*4^10, p*q)),前者是dfs构建Trie树操作, 后者是搜索words字符串操作
额外空间复杂度: O(max(m*n, p*q)), 前者是保存当前board字符占用的临时树组空间开销,后者是保存Trie树的空间开销。
Trie root;int h;int w;char[][] board;Set<String> searched;public List<String> findWords(char[][] board, String[] words) {h = board.length;w = board[0].length;searched = new HashSet<>();this.board = board;root = new Trie();int[] firstCharArray = new int[26];for (String word : words) {firstCharArray[word.charAt(0) - 'a'] = 1;}for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {if (firstCharArray[board[i][j] - 'a'] == 0) {continue;}int[][] usedMap = new int[h][w];StringBuilder sb = new StringBuilder(board[i][j]);dfs(sb, i, j, usedMap);}}List<String> result = new ArrayList<>();for (String word : words) {Trie current = root;for (char c : word.toCharArray()) {if (current.nextList[c-'a'] != null) {current = current.nextList[c-'a'];} else {current = null;break;}}if (current != null && current.end) {result.add(word);}}return result;}private void dfs(StringBuilder sb, int i, int j, int[][] usedMap) {if (sb.length() >= 10 || i < 0 || i >= h || j < 0 || j>=w || usedMap[i][j] == 1) {String s = sb.toString();if (!searched.contains(s)) {searched.add(s);addWord(s);}return;}usedMap[i][j] = 1;sb.append(board[i][j]);boolean hasWay = false;if(i - 1 >=0) {hasWay = true;dfs(sb, i-1, j, usedMap);}if(i + 1 < h) {hasWay = true;dfs(sb, i+1, j, usedMap);}if(j - 1 >=0) {hasWay = true;dfs(sb, i, j-1, usedMap);}if(j + 1 < w) {hasWay = true;dfs(sb, i, j+1, usedMap);}if (!hasWay && !searched.contains(sb.toString())) {searched.add(sb.toString());addWord(sb.toString());}usedMap[i][j] = 0;sb.delete(sb.length()-1, sb.length());}public void addWord(String word) {Trie current = root;for (char c : word.toCharArray()) {if (current.nextList[c - 'a'] != null) {current = current.nextList[c - 'a'];} else {Trie next = new Trie();next.end = true;current.nextList[c - 'a'] = next;current = next;}}current.value = word;current.end = true;}class Trie {boolean end;String value;Trie[] nextList;public Trie() {this.end = false;this.nextList = new Trie[26];}}
写法2
除了对board进行Trie树构建,还有一种方法是对words树组进行Trie树构建,并在此树上通过对board进行dfs+回溯搜索的做法。这种做法时间复杂度上更有优势,因为在dfs时能够更加快速的收敛。写法1可能会遍历很多无效的字符串。
必须强调的是,由于回溯会将占用的字符复原,我们其实可以在board上记录哪些字符被占用,这节省了一部分空间。
而且Trie树节点也无需用end标识该节点是否是字符串终止节点,可以直接拿value的值替代,如果value为空,则没有字符串在该字符上终止,否则有。
Trie root;int h;int w;char[][] board;List<String> result;int[][] directions;public List<String> findWords(char[][] board, String[] words) {h = board.length;w = board[0].length;this.board = board;root = new Trie();directions = new int[][]{{1, 0}, {-2, 0}, {1, 1}, {0, -2}};for (String word : words) {addWord(word);}result = new ArrayList<>();for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {dfs(i,j,root);}}return result;}private void dfs(int i, int j, Trie root) {char temp = board[i][j];if (board[i][j] == '$' || root.nextList[temp - 'a'] == null) {return;}Trie trie = root.nextList[temp - 'a'];if (trie.value != null) {result.add(trie.value);trie.value = null;}board[i][j] = '$';for (int[] direction : directions) {i += direction[0];j += direction[1];if (i < 0 || i >= h || j < 0 || j>=w) {continue;}dfs(i, j, trie);}board[i][j+1] = temp;}public void addWord(String word) {Trie current = root;for (char c : word.toCharArray()) {if (current.nextList[c - 'a'] == null) {current.nextList[c - 'a'] = new Trie();}current = current.nextList[c - 'a'];}current.value = word;}class Trie {boolean end;String value;Trie[] nextList;public Trie() {this.end = false;this.nextList = new Trie[26];}}
在board 为 m*n 大小,words 长度为p,每个字符串平均长度为q的情况下:
时间复杂度: O(max(m*n*3^10), p*q),前者是dfs构建Trie树操作, 后者是搜索words字符串操作
额外空间复杂度: O(p*q), 保存Trie树的空间开销。
这篇关于Leetcode. 212 单词搜索II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!