拼字游戏
这道题其实就是dfs，思路也是挺清晰的，但是实现代码就麻烦些了，最后也是看答案才摸清套路
我的思路基本和答案差不多，首先是利用for loop遍历每个字符，然后从这个字符开始找到该字符为起点的最大匹配的数目，接下来就是遍历每个字符的最大数目，从这些中取最大的。
两层dfs嵌套
外层dfs, 遍历每个字符，
找到以这个字符开始的所有匹配的单词的坐标位置List<List<Integer>>，
遍历这个list of list,
每个list其实就是一个单词，用stringbuilder把一个单词拼接起来，同时把这些字符标记访问，然后把单词装进过渡容器中，和结果容器比较下大小，如果其大小超越了结果，那么说明有更多的组合出现，让其替代结果容器。 然后进行dfs（）其意义就是如果当前匹配的是上述单词，那就把后面开头的字符的匹配最大情况都找到。
内层dfs 较为简单，就是一个利用字典树去找以某个字符开头的所有匹配的情况，将坐标化成数字，利用list<Integer>表示矩阵上的一个单词。找到所有可能的匹配。
代码如下
public class Solution {
/*
* @param board: a list of lists of character
* @param words: a list of string
* @return: an integer
*/
public int boggleGame(char[][] board, String[] words) {
// write your code here
Trie t;
t = new Trie();
Trie t1 = t;
buildT(words, t);
int m = board.length;
int n = board[0].length;
boolean[][] visited = new boolean[m][n];
List<String> result = new ArrayList<>();
List<String> path = new ArrayList<>();
findWords(result, board, visited, path, 0, 0, t);
return result.size();
}
private void findWords(List<String> result, char[][] board, boolean[][] visited, List<String> path, int x, int y, Trie t){
int m = board.length;
int n = board[0].length;
for(int i = x; i < m; i++){
for(int j = y; j < n; j++){
//得到该位置为起点的所有在词典中的字符串的下标
if(visited[i][j]){
continue;
}
List<List<Integer>> ListOfIndexs = new ArrayList<>();
List<Integer> newP = new ArrayList<>();
getNextWords(ListOfIndexs, board, visited, newP, i, j, t);
for(List<Integer> indexs: ListOfIndexs){
StringBuilder sb = new StringBuilder();
for(int index: indexs){
visited[index/n][index%n] = true;
sb.append(board[index/n][index%n]);
}
String str = sb.toString();
path.add(str);
if(path.size() > result.size()){
result.clear();
result.addAll(path);
}
findWords(result, board, visited, path, i, j + 1, t);
path.remove(path.size() - 1);
for(int index: indexs){
visited[index/n][index%n] = false;
}
}
}
// 上面递归会导致穿进去的j 成为递归内的内循环起点，要在下一行归零
y = 0;
}
}
int []dx = {0, 1, 0, -1};
int []dy = {1, 0, -1, 0};
private void getNextWords(List<List<Integer>> words, char[][] board,boolean[][] visited, List<Integer> path, int x, int y, Trie t){
if(x < 0 | x >= board.length || y < 0 || y >= board[0].length
|| visited[x][y] == true || t.tries[board[x][y] - 'a'] == null) {
return;
}
t = t.tries[board[x][y] - 'a'];
if(t.word != null){
List<Integer> newP = new ArrayList<>(path);
newP.add(x * board[0].length + y);
words.add(newP);
return;
}
path.add(x * board[0].length + y);
visited[x][y] = true;
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
getNextWords(words, board, visited, path, nx, ny, t);
}
visited[x][y] = false;
path.remove(path.size() - 1);
}
private void buildT(String[] words, Trie t){
for(String word: words){
Trie p = t;
char[] strs = word.toCharArray();
for(int i = 0; i < strs.length; i++){
int index = strs[i] - 'a';
if(p.tries[index] == null){
p.tries[index] = new Trie();
}
p = p.tries[index];
}
p.word = word;
}
}
}
class Trie{
String word = null;
Trie[] tries = new Trie[26];
}
