LeetCode212——单词搜索II
我的LeetCode代码仓:https://github.com/617076674/LeetCode
原题链接:https://leetcode-cn.com/problems/word-search-ii/description/
题目描述:
知识点:回溯、Trie
思路一:LeetCode079——单词搜索的加强版
时间复杂度是O(s),其中s为words数组中的字符总数。空间复杂度是O(mn),其中m为board数组的行数,n为board数组的列数。
JAVA代码:
public class Solution {
boolean[][] flag;
int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
private boolean exist(char[][] board, String word) {
int m = board.length;
if(m == 0){
return word.length() == 0;
}
int n = board[0].length;
flag = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if(board[i][j] == word.charAt(0)){
flag[i][j] = true;
if(exist(board, word, 1, i, j)){
return true;
}
flag[i][j] = false;
}
}
}
return false;
}
//We have found [0, index] of word in board, trying to find index + 1.
//Now we are in (x, y)
private boolean exist(char[][] board, String word, int index, int x, int y){
if(index == word.length()){
return true;
}
for (int i = 0; i < directions.length; i++) {
int newX = x + directions[i][0];
int newY = y + directions[i][1];
if(newX >=0 && newX < board.length && newY >= 0 && newY < board[0].length){
if(!flag[newX][newY] && board[newX][newY] == word.charAt(index)){
flag[newX][newY] = true;
if(exist(board, word, index + 1, newX, newY)){
return true;
}
flag[newX][newY] = false;
}
}
}
return false;
}
public List<String> findWords(char[][] board, String[] words) {
Set<String> result = new HashSet<>();
for (int i = 0; i < words.length; i++) {
if(exist(board, words[i])){
result.add(words[i]);
}
}
return new ArrayList<>(result);
}
}
LeetCode解题报告:
思路二:用Trie进行优化
首先将words数组中的单词存储进一个Trie数据结构中,再进行回溯寻找。
时间复杂度和空间复杂度与所给的words数组中的单词有关。
JAVA代码:
public class Solution {
List<String> result = new ArrayList<>();
public List<String> findWords(char[][] board, String[] words) {
TrieNode trieNode = buildTrie(words);
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
dfs (board, i, j, trieNode);
}
}
return result;
}
public void dfs(char[][] board, int i, int j, TrieNode trieNode) {
char c = board[i][j];
if ('#' == c || null == trieNode.next[c - 'a']) return;
trieNode = trieNode.next[c - 'a'];
if (null != trieNode.word) {
result.add(trieNode.word);
trieNode.word = null; //去重
}
board[i][j] = '#';
if (i > 0) dfs(board, i - 1, j ,trieNode);
if (j > 0) dfs(board, i, j - 1, trieNode);
if (i < board.length - 1) dfs(board, i + 1, j, trieNode);
if (j < board[0].length - 1) dfs(board, i, j + 1, trieNode);
board[i][j] = c;
}
private class TrieNode {
private TrieNode[] next = new TrieNode[26];
private String word;
}
public TrieNode buildTrie(String[] words) {
TrieNode root = new TrieNode();
for (String word : words) {
TrieNode trieNode = root;
for (char c : word.toCharArray()) {
int i = c - 'a';
if (null == trieNode.next[i]) {
trieNode.next[i] = new TrieNode();
}
trieNode = trieNode.next[i];
}
trieNode.word = word;
}
return root;
}
}
LeetCode解题报告: