General idea: backtracking (dfs).
Use DFS to find each word in the board -> 每个单词都要进行一遍dfs
参考 79. Word Search, 一样的解法
Time complexity: O(sum(m * n * 4^l)), board size is m * n, word max length is l. For every word, time is O(m * n * 4^l).
Total time complexity for all words is the sum of all time complexities for every word.
Space complexity: O(l)
class Solution {
public List<String> findWords(char[][] board, String[] words) {
List<String> res = new ArrayList<>();
if (board.length == 0 || board[0].length == 0) {
return res;
}
for (String word : words) {
if (exist(board, word)) {
res.add(word);
}
}
return res;
}
private boolean exist(char[][] board, String word) {
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (search (i, j, 0, board, word)) {
return true;
}
}
}
return false;
}
private boolean search(int i, int j, int index, char[][] board, String word) {
if (index == word.length()) {
return true;
}
if (i < 0 || j < 0 || i > board.length - 1 || j > board[0].length - 1) { // 剪枝
return false;
}
if (board[i][j] != word.charAt(index)) { // 剪枝
return false;
}
char cur = board[i][j];
board[i][j] = '#';
boolean found = search(i - 1, j, index + 1, board, word)
|| search(i + 1, j, index + 1, board, word)
|| search(i, j - 1, index + 1, board, word)
|| search(i, j + 1, index + 1, board, word);
board[i][j] = cur;
return found;
}
}
Build a trie of the dictionary and use DFS to traverse the board, the path must also exist in trie.
用trie记录word路径，不需要每个单词都做一遍backtracking。如果有前缀相同的单词，优势明显。
参考这个帖子, 不是空间最优解，但是比较好理解。
Trie 的实现见 208. Implement Trie (Prefix Tree)
Time complexity: O(m * n * 4^l)
Space complexity: O(sum(l)), the total length of all the words
class Solution {
public List<String> findWords(char[][] board, String[] words) {
Set<String> res = new HashSet<>(); // 注意去重
if (board == null || board.length == 0 || board[0].length == 0 || words == null || words.length == 0) {
return new ArrayList<>(res);
}
Trie trie = new Trie();
for (String word : words) {
trie.insert(word);
}
boolean[][] visited = new boolean[board.length][board[0].length];
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
search (i, j, "", trie, board, visited, res);
}
}
return new ArrayList<>(res);
}
private void search(int i, int j, String s, Trie trie, char[][] board, boolean[][] visited, Set<String> res) {
if (i < 0 || j < 0 || i > board.length - 1 || j > board[0].length - 1 || visited[i][j]) {
return;
}
s += board[i][j];
if (!trie.startsWith(s)) {
return;
}
if (trie.search(s)) {
res.add(s);
}
visited[i][j] = true;
search(i - 1, j, s, trie, board, visited, res);
search(i + 1, j, s, trie, board, visited, res);
search(i, j - 1, s, trie, board, visited, res);
search(i, j + 1, s, trie, board, visited, res);
visited[i][j] = false;
}
}