问题
直觉：因为我们必须通过上/下/左/右方式遍历来找到单词数组中存在的单词（在网格/板上）。
可以使用回溯来完成遍历
为了搜索单词，我们可以使用 trie，因为这也可以通过检查树中是否存在前缀来帮助我们进行早期识别。这是避免不必要的遍历板（即遍历板没有意义，如果前缀不存在于特里树中，那么使用前缀的字符串或单词形式也不会出现在特里树中）
方法：我们将所有单词[]放入trie树中，然后遍历棋盘中的每个单元格(i,j)，并在所有4个方向上形成各种字符串，然后将所有列表中 trie 中存在的字符串。
js+ajax关键词搜索条件筛选内容列表代码
一款js+ajax关键词搜索条件筛选内容列表代码
24 查看详情
class Solution { public List 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 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 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 = 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的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/886291.html
微信扫一扫 
支付宝扫一扫 
