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