表情网站源码,找企业做网站,土巴兔装修口碑怎样,网片式防护围栏算法-单词搜索 II
1 题目概述
1.1 题目出处
https://leetcode.cn/problems/word-search-ii/description/?envTypestudy-plan-v2envIdtop-interview-150
1.2 题目描述 2 DFS
2.1 解题思路
每个格子往上下左右四个方向DFS#xff0c;拼接后的单词如果在答案集中study-plan-v2envIdtop-interview-150
1.2 题目描述 2 DFS
2.1 解题思路
每个格子往上下左右四个方向DFS拼接后的单词如果在答案集中则记录下来。
同时为了避免DFS时往回找需要记录下已访问记录。
2.2 代码
class Solution {private SetString wordSet new HashSet();private ListString resultList new LinkedList();public ListString findWords(char[][] board, String[] words) {for (String word : words) {wordSet.add(word);}StringBuilder sb new StringBuilder();char[][] visitSet new char[board.length][board[0].length];for (int i 0; i board.length; i) {for (int j 0; j board[0].length; j) {dfs(i, j, board, sb, visitSet);}}return resultList;}private void dfs(int i, int j, char[][] board, StringBuilder sb, char[][] visitSet) {if (sb.length() 10) {return;}if (visitSet[i][j] 1) {return;}visitSet[i][j] 1;sb.append(board[i][j]);String currentStr sb.toString();if (wordSet.contains(currentStr)) {resultList.add(currentStr);wordSet.remove(currentStr);}if (i 0) {dfs(i - 1, j, board, sb, visitSet);}if (i board.length - 1) {dfs(i 1, j, board, sb, visitSet);}if (j 0) {dfs(i, j - 1, board, sb, visitSet);}if (j board[0].length - 1) {dfs(i, j 1, board, sb, visitSet);}sb.deleteCharAt(sb.length() - 1);visitSet[i][j] 0;}
}2.3 时间复杂度 O(M * N * 4^10) 字符串最多10
2.4 空间复杂度
O(10)
3 DFSTrie树
3.1 解题思路
3.2 代码
class Solution {private SetString wordSet new HashSet();private ListString resultList new LinkedList();public ListString findWords(char[][] board, String[] words) {for (String word : words) {wordSet.add(word);}StringBuilder sb new StringBuilder();char[][] visitSet new char[board.length][board[0].length];for (int i 0; i board.length; i) {for (int j 0; j board[0].length; j) {dfs(i, j, board, sb, visitSet);}}return resultList;}private void dfs(int i, int j, char[][] board, StringBuilder sb, char[][] visitSet) {if (sb.length() 10) {return;}if (visitSet[i][j] 1) {return;}visitSet[i][j] 1;sb.append(board[i][j]);String currentStr sb.toString();if (wordSet.contains(currentStr)) {resultList.add(currentStr);wordSet.remove(currentStr);}if (i 0) {dfs(i - 1, j, board, sb, visitSet);}if (i board.length - 1) {dfs(i 1, j, board, sb, visitSet);}if (j 0) {dfs(i, j - 1, board, sb, visitSet);}if (j board[0].length - 1) {dfs(i, j 1, board, sb, visitSet);}sb.deleteCharAt(sb.length() - 1);visitSet[i][j] 0;}
}3.3 时间复杂度 4 DFSTrie树 优化
4.1 解题思路
4.2 代码
class Solution {private ListString resultList new LinkedList();private TrieNode trieNode new TrieNode();static class TrieNode {private TrieNode[] trieNodes new TrieNode[26];public boolean isWord false;public void insert(String word) {if (word.length() 0) {isWord true;return;}int index word.charAt(0) - a;if (null trieNodes[index]) {trieNodes[index] new TrieNode();}trieNodes[index].insert(word.substring(1));}}public ListString findWords(char[][] board, String[] words) {for (String word : words) {trieNode.insert(word);}StringBuilder sb new StringBuilder();char[][] visitSet new char[board.length][board[0].length];for (int i 0; i board.length; i) {for (int j 0; j board[0].length; j) {dfs(i, j, board, sb, visitSet, trieNode);}}return resultList;}private void dfs(int i, int j, char[][] board, StringBuilder sb, char[][] visitSet, TrieNode ct) {if (sb.length() 10) {return;}if (visitSet[i][j] 1) {return;}visitSet[i][j] 1;sb.append(board[i][j]);ct ct.trieNodes[board[i][j] - a];if (null ! ct) {if (ct.isWord) {resultList.add(sb.toString());ct.isWord false;} if (i 0) {dfs(i - 1, j, board, sb, visitSet, ct);}if (i board.length - 1) {dfs(i 1, j, board, sb, visitSet, ct);}if (j 0) {dfs(i, j - 1, board, sb, visitSet, ct);}if (j board[0].length - 1) {dfs(i, j 1, board, sb, visitSet, ct);}}sb.deleteCharAt(sb.length() - 1);visitSet[i][j] 0;}
}4.3 时间复杂度 参考文档
