問題
直覺：因為我們必須透過上/下/左/右方式遍歷來找到單字數組中存在的單字（在網格/板上）。
可以使用回溯來完成遍歷
為了搜尋單字，我們可以使用 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中文網其他相關文章！
