给定一个 m x n 的字符板和一个字符串单词列表，返回板上的所有单词。
每个单词必须由顺序相邻的单元格的字母构成，其中相邻的单元格水平或垂直相邻。同一字母单元不得在一个单词中使用多次。
蛮力方法：时间复杂度将为O(词数 * M * 4 * 3^L-1)
public class WordSearchII {
int flag = 0;
public List<String> findWords(char[][] b, String[] words) {
List<String> result = new ArrayList<>();
for (int k = 0; k < words.length; k++) {
flag = 0;
/*
* Find word's first letter. Then call method to check it's surroundings
*/
for (int r = 0; r < b.length; r++) {
for (int c = 0; c < b[0].length; c++) {
if (b[r][c] == words[k].charAt(0) && dfs(b, words[k], 0, r, c)) {
if (flag == 1) {
result.add(words[k]);
break;
}
}
}
if (flag == 1) {
break;
}
}
}
return result;
// return new ArrayList<>(new HashSet<>(result));
}
public boolean dfs(char[][] b, String word, int start, int r, int c) {
/* once we get past word.length, we are done. */
if (word.length() <= start) {
flag = 1;
return true;
}
/*
* if off bounds, letter is seen, letter is unequal to word.charAt(start)
* return false
*/
if (r < 0 || c < 0 || r >= b.length || c >= b[0].length || b[r][c] == '0' || b[r][c] != word.charAt(start))
return false;
/* set this board position to seen. (Because we can use this postion) */
char tmp = b[r][c];
b[r][c] = '0';
/* recursion on all 4 sides for next letter, if works: return true */
if (dfs(b, word, start + 1, r + 1, c) || dfs(b, word, start + 1, r - 1, c) || dfs(b, word, start + 1, r, c + 1)
|| dfs(b, word, start + 1, r, c - 1)) {
// Set back to unseen
b[r][c] = tmp;
return true;
}
// Set back to unseen
b[r][c] = tmp;
return false;
}
}
基于字典树的方法
public class WordSearchIIWithTwist {
char[][] _board = null;
ArrayList<String> _result = new ArrayList<String>();
TrieNode root = new TrieNode();
public List<String> findWords(char[][] board, String[] words) {
// Step 1). Construct the Trie
for (int i = 0; i < words.length; i++) {
char[] arr = words[i].toCharArray();
TrieNode current = root;
for (int j = 0; j < arr.length; j++) {
if (!current.children.containsKey(arr[j])) {
current.children.put(arr[j], new TrieNode());
}
current = current.children.get(arr[j]);
}
current.word = words[i];
}
this._board = board;
// Step 2). Backtracking starting for each cell in the board
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (root.children.containsKey(board[i][j])) {
dfs(i, j, root);
}
}
}
return _result;
}
private void dfs(int row, int col, TrieNode parent) {
if (row < 0 || col < 0 || row >= _board.length || col >= _board[0].length || _board[row][col] == '#') {
return;
}
char letter = this._board[row][col];
if (!parent.children.containsKey(letter)) {
return;
}
TrieNode nextNode = parent.children.get(letter);
// check if there is any match
if (nextNode.word != null) {
_result.add(nextNode.word);
nextNode.word = null;
}
// mark the current letter before the EXPLORATION
this._board[row][col] = '#';
// explore neighbor cells in 4 directions: up, down, left, right
dfs(row + 1, col, nextNode);
dfs(row - 1, col, nextNode);
dfs(row, col - 1, nextNode);
dfs(row, col + 1, nextNode);
this._board[row][col] = letter;
}
public static void main(String[] args) {
WordSearchIIWithTwist a = new WordSearchIIWithTwist();
System.out.println(a.findWords(new char[][] { { 'a' } }, new String[] { "a" }));
}
}
class TrieNode {
Map<Character, TrieNode> children = new HashMap<>();
String word = null;
public TrieNode() {
};
}
这是一种替代解决方案，具有增强的节点结构，使代码更简单。
我将由您决定哪个更适合您的需求：
import java.util.*;
public class Solution {
private char[][] board = null;
private boolean[][] visited = null;
private final Set<String> result = new HashSet<>();
int[][]directions = {{0,1},{1,0},{0,-1},{-1,0}};
public List<String> findWords(char[][] board, String[] words) {
List<Node> wordsAsNodes = new ArrayList<>();
for (String word : words) {
wordsAsNodes.add(new Node(word));
}
this.board = board;
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
final int ii=i, jj=j;
wordsAsNodes.forEach(node->{
if(node.c == board[ii][jj]){
visited = initializeVisited();
dfs(ii, jj, node);
}
});
}
}
return new ArrayList<>(result);
}
private boolean[][] initializeVisited() {
visited = new boolean[board.length][board[0].length];
for(boolean[] row : visited){
Arrays.fill(row, false);
}
return visited;
}
private void dfs(int row, int col, Node node) {
if (node == null || row < 0 || col < 0 || row >= board.length ||
col >= board[0].length || visited[row][col]) return;
char letter = board[row][col];
if (node.c != letter) return;
visited[row][col] = true;
Node nextNode = node.getNext();
// check if there is any match
if (nextNode == null) {
result.add(node.word);
return;
}
// explore neighbor cells in 4 directions
for(int[] dir : directions){
dfs(row + dir[0], col + dir[1], nextNode);
}
//if no solution found mark as unvisited for following attempts
visited[row][col] = false;
}
public static void main(String[] args) {
Solution a = new Solution();
char[][] board1 ={
{'o','a','a','n'},
{'e','t','a','e'},
{'i','h','k','r'},
{'i','f','l','v'}
};
String [] words1 = {"oath","pea","eat","rain"};
System.out.println(a.findWords(board1, words1));
}
}
class Node {
final String word;
private final int index;
private Node parent, next;
char c;
public Node(String word) {
this(word,0);
}
private Node(String word, int index) {
this.word = Objects.requireNonNull(word, "word should not be null");
this.index = index;
c = word.charAt(index);
}
private Node next() {
return index +1 < word.length() ? new Node(word, index+1) : null;
}
private Node parent() {
return index -1 >= 0 ? new Node(word, index-1) : null;
}
Node getParent() {
return parent == null ? parent = parent(): parent;
}
Node getNext() {
return next == null ? next = next(): next;
}
@Override
public String toString() {
return c +" index "+ index + " in " + word ;
}
}
您可能想要使用 Trie 的原因是您可以使用 TRIE 来索引整个板（尽管创建这个 trie 并不简单），在创建 trie 后，您可以在 O(1) 时间内找到其中的任何单词
board = { T H
M E}
trieBeforeDict =
-root-
|------------------------------\--------------\--\
T H M E
|------ | ..etc..
|-------\---\ \--\--\
H M E T M E
|--\ ..etc.. ..etc..
M E
| |
E M
traverse with dictionary
* marks isWord attribute
trieAfterDict =
-root-
|--\--\
T H M
| | |
| E* E*
H |
| M*
|
E*
|
M*
初始化后，您可以丢弃棋盘和字典，以后的任何查找都会非常快，并且内存开销很低。
想要这样做的一个原因可能是您希望最大限度地减少游戏中的开销，并可以选择在开发中预编译“游戏”，并将“已编译”的 trie 发送到生产环境
单词搜索1：在网格中搜索一个单词。
单词搜索需要从每个单元格开始查找单词。
优化1：利用回溯提前终止无效搜索。
单词搜索2：在网格中搜索多个单词。
对于每个单词，应用回溯。
优化2：一次解析，一次性查找所有单词。在每个单元格中，trie 帮助找出是否有任何单词匹配。