给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
示例：
输入:
words = ["oath","pea","eat","rain"] and board =
[
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]
输出: ["eat","oath"]
解题思路：
要在一个二维矩阵里面找到所有可能的单词，最简单的方法就是穷举，现在的问题就是如何穷举所有的单词，我们用回溯，也就是从一个字符开始，依次探索它的四个方向，就像迷宫问题一样，当一个方向走完时，就回退一步，选择其他方向，就像迷宫问题一样
完整代码如下：
import java.util.ArrayList;
import java.util.Arrays;
class Solution {
public ArrayList<String> findWords(char[][] board, String[] words) {
StringBuilder word = new StringBuilder(); //用来存放探索到的单词
ArrayList<String> res = new ArrayList<String>();//结果集
ArrayList<String> Words = new ArrayList<String>();//主要是为了contains的方法
boolean[][] used = new boolean[board.length][board[0].length];//用过的字符在一个单词中不能再次被使用
for(String tmp : words)
Words.add(tmp);
for(int i=0; i<board.length; i++)//从每一个点开始遍历查找
for(int j=0; j<board[0].length; j++)
{
used[i][j]=true; //true表示已被使用
word.append(board[i][j]); //加入字符串中
backtrack(board,used,Words,word,res,i,j);
word.deleteCharAt(word.length()-1);//删除该字符
used[i][j]=false;//置为未使用
}
return res;
}
public void backtrack(char[][] board, boolean[][] used, ArrayList<String> Words, StringBuilder word, ArrayList<String> res, int r, int c)
{
if(Words.contains(word.toString())) //如果探索到的字符串在单词表里
{
if(Words.contains(word.toString()) && !res.contains(word.toString()))
res.add(word.toString());
//加入结果集中，不重复加入
}
for(int i=0; i<4; i++) //四个方向探索
{
switch(i)
{
case 0:
if(c-1>=0)
if(!used[r][c-1])
{
used[r][c-1]=true;
word.append(board[r][c-1]);
backtrack(board,used,Words,word,res,r,c-1);
word.deleteCharAt(word.length()-1);
used[r][c-1]=false;
//同理
}
break;
case 1:
if(r-1>=0)
if(!used[r-1][c])
{
used[r-1][c]=true;
word.append(board[r-1][c]);
backtrack(board,used,Words,word,res,r-1,c);
word.deleteCharAt(word.length()-1);
used[r-1][c]=false;
}
break;
case 2:
if(c+1<board[0].length)
if(!used[r][c+1])
{
used[r][c+1]=true;
word.append(board[r][c+1]);
backtrack(board,used,Words,word,res,r,c+1);
word.deleteCharAt(word.length()-1);
used[r][c+1]=false;
}
break;
case 3:
if(r+1<board.length)
if(!used[r+1][c])
{
used[r+1][c]=true;
word.append(board[r+1][c]);
backtrack(board,used,Words,word,res,r+1,c);
word.deleteCharAt(word.length()-1);
used[r+1][c]=false;
}
break;
}
}
}
}
这个解法超时了，因为做了太多的无用功，比如说，现在我从一个字符a开始探索，然而，单词表里的所有单词没有一个是以a开头的，那我们接下来的做的是不是都是无用功，因此我们希望能够通过前缀来决定应该探索哪个方向，这可以通过一个树结构来实现，树的结构为：
class TrieNode
{
HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>();
//该结构用来存放孩子结点
String word = null; //遍历到当前位置时的字符串
public TrieNode() {}
}
树的结构类似于：
现在要做的就是构造该树
// Step 1). Construct the Trie
TrieNode root = new TrieNode();
for (String word : words) 首先从单词表里取出一个单词
{
TrieNode node = root; //从根结点开始
for(Character letter : word.toCharArray()) //取出单词里面的每一个字符
{
if (node.children.containsKey(letter)) //如果该字符已经在树上
{
node = node.children.get(letter); //将node置为树上对应的结点
}
else
{
TrieNode newNode = new TrieNode(); //新建一个结点
node.children.put(letter, newNode); //加入到node结点上
node = newNode; //将node置为新增结点
}
}
node.word = word; // store words in Trie //当一个单词的所有结点遍历完时，当前结点回溯到根节点就是该单词，所以将word置为该单词
}
最后一步，我们要写的就是回溯函数，回溯函数应该怎么写？首先要从一个字符开始，然后找它的四个方向，如果一个方向对应的字符不在树上，就找下一个方向
private void backtracking(int row, int col, TrieNode parent)
{
Character letter = this._board[row][col]; //取出当前字符
TrieNode currNode = parent.children.get(letter);//找到当前字符在树上的结点
// check if there is any match
if (currNode.word != null)
{
//如果该结点的字符串不是空，说明是一个单词，将该单词加入结果集里面
this._result.add(currNode.word);
currNode.word = null;
}
// mark the current letter before the EXPLORATION
this._board[row][col] = '#'; //将一个位置设为不可走
// explore neighbor cells in around-clock directions: up, right, down, left
int[] rowOffset = {-1, 0, 1, 0};
int[] colOffset = {0, 1, 0, -1};
四个方向的偏差
for (int i = 0; i < 4; ++i)
{ //找四个方向
int newRow = row + rowOffset[i];
int newCol = col + colOffset[i];
if (newRow < 0 || newRow >= this._board.length || newCol < 0
|| newCol >= this._board[0].length)
{
continue;
}
//越界处理
if (currNode.children.containsKey(this._board[newRow][newCol])) //如果该字符在树上，就可以往下探索
{
backtracking(newRow, newCol, currNode);
}
}
// End of EXPLORATION, restore the original letter in the board.
this._board[row][col] = letter; //重新置为可走
// Optimization: incrementally remove the leaf nodes
if (currNode.children.isEmpty())
{
parent.children.remove(letter); //剪枝，因为如果一个结点的所有孩子都为空，而且该结点已经被探索过了，就可以剪掉
}
}
完整代码：
class TrieNode {
HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>();
String word = null;
public TrieNode() {}
}
class Solution {
char[][] _board = null;
ArrayList<String> _result = new ArrayList<String>();
public List<String> findWords(char[][] board, String[] words) {
// Step 1). Construct the Trie
TrieNode root = new TrieNode();
for (String word : words) {
TrieNode node = root;
for (Character letter : word.toCharArray()) {
if (node.children.containsKey(letter)) {
node = node.children.get(letter);
} else {
TrieNode newNode = new TrieNode();
node.children.put(letter, newNode);
node = newNode;
}
}
node.word = word; // store words in Trie
}
this._board = board;
// Step 2). Backtracking starting for each cell in the board
for (int row = 0; row < board.length; ++row) {
for (int col = 0; col < board[row].length; ++col) {
if (root.children.containsKey(board[row][col])) {
backtracking(row, col, root);
}
}
}
return this._result;
}
private void backtracking(int row, int col, TrieNode parent) {
Character letter = this._board[row][col];
TrieNode currNode = parent.children.get(letter);
// check if there is any match
if (currNode.word != null) {
this._result.add(currNode.word);
currNode.word = null;
}
// mark the current letter before the EXPLORATION
this._board[row][col] = '#';
// explore neighbor cells in around-clock directions: up, right, down, left
int[] rowOffset = {-1, 0, 1, 0};
int[] colOffset = {0, 1, 0, -1};
for (int i = 0; i < 4; ++i) {
int newRow = row + rowOffset[i];
int newCol = col + colOffset[i];
if (newRow < 0 || newRow >= this._board.length || newCol < 0
|| newCol >= this._board[0].length) {
continue;
}
if (currNode.children.containsKey(this._board[newRow][newCol])) {
backtracking(newRow, newCol, currNode);
}
}
// End of EXPLORATION, restore the original letter in the board.
this._board[row][col] = letter;
// Optimization: incrementally remove the leaf nodes
if (currNode.children.isEmpty()) {
parent.children.remove(letter);
}
}
}
做了六七道中等难度的题，感觉就是中等难度一般不用优化就能过了，但是困难难度如果没有优化，就会超时，做了两三道都是这样，其实基本思路还是挺简单的，就是回溯
作者：LeetCode
链接：https://leetcode-cn.com/problems/word-search-ii/solution/dan-ci-sou-suo-ii-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。