问题
直觉：因为我们必须通过上/下/左/右方式遍历来找到单词数组中存在的单词（在网格/板上）。
可以使用回溯来完成遍历
为了搜索单词，我们可以使用 trie，因为这也可以通过检查树中是否存在前缀来帮助我们进行早期识别。这是避免不必要的遍历棋盘（即遍历棋盘没有意义，如果前缀不存在于特里树中，那么使用前缀的字符串或单词形式也不会出现在特里树中）
方法：我们将所有单词[]放入trie树中，然后遍历棋盘中的每个单元格(i,j)，并在所有4个方向上形成各种字符串，然后将所有列表中 trie 中存在的字符串。
class Solution {
public List<String> findWords(char[][] board, String[] words) {
int max = 0;
Trie t = new Trie();
for (String w : words) {
t.insert(w);
}
int arr[][] = new int[board.length][board[0].length];
StringBuilder str = new StringBuilder();
Set<String> list = new HashSet<>();// to have only unique strings/words
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
// recursively traverse all the cells to find the words
traverse(i, j, board, arr, arr.length, arr[0].length, t, str, list);
}
}
return new ArrayList<>(list);
}
public void traverse(int i, int j, char b[][], int arr[][], int n, int m, Trie t, StringBuilder str,Set<String> list) {
str.append(b[i][j]);// add current cell character to form a potential prefix/word
if (!t.startWith(str.toString())) {//early checking of prefix before moving forward to avoid un-necessary traversal
str.deleteCharAt(str.length() - 1);
return;
}
if (t.present(str.toString()))
list.add(str.toString());
arr[i][j] = 1;// mark current cell visited to avoid visiting the same cell the current recursive call stack
int dirs[][] = { { 0, -1 }, { 0, 1 }, { -1, 0 }, { 1, 0 } };// left,right,up,down
for (int dir[] : dirs) {
int I = i + dir[0];
int J = j + dir[1];
if (I < n && J < m && I >= 0 && J >= 0 && arr[I][J] == 0) {
traverse(I, J, b, arr, n, m, t, str, list);
}
}
arr[i][j] =0;// mark unvisited
str.deleteCharAt(str.length()-1);// remove the last added character
}
}
class Node {
Node node[] = new Node[26];
boolean flag;
public boolean isPresent(char c) {
return node[c - 'a'] != null;
}
public Node get(char c) {
return node[c - 'a'];
}
public void add(char c, Node n) {
node[c - 'a'] = n;
}
public void setFlag() {
this.flag = true;
}
public boolean getFlag() {
return this.flag;
}
}
class Trie {
Node root;
public Trie() {
root = new Node();
}
public void insert(String s) {
Node node = root;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (!node.isPresent(c)) {
node.add(c, new Node());
}
node = node.get(c);
}
node.setFlag();
}
public boolean present(String s) {
Node node = root;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (!node.isPresent(c)) {
return false;
}
node = node.get(c);
}
return node.getFlag();
}
public boolean startWith(String s) {
Node node = root;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (!node.isPresent(c)) {
return false;
}
node = node.get(c);
}
return true;
}
}
以上是单词搜索 II的详细内容。更多信息请关注PHP中文网其他相关文章！
