单词搜索II

给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中"相邻"单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

示例:

输入:

words = ["oath","pea","eat","rain"] and board =

[

['o','a','a','n'],

['e','t','a','e'],

['i','h','k','r'],

['i','f','l','v']

]

输出: ["eat","oath"]

说明:
你可以假设所有输入都由小写字母 a-z 组成。

提示:

你需要优化回溯算法以通过更大数据量的测试。你能否早点停止回溯？
如果当前单词不存在于所有单词的前缀中，则可以立即停止回溯。什么样的数据结构可以有效地执行这样的操作？散列表是否可行？为什么？前缀树如何？如果你想学习如何实现一个基本的前缀树，请先查看这个问题：实现Trie（前缀树）。

方法：前缀树+深度优先搜索。

 import java.util.ArrayList;

 import java.util.HashSet;

 import java.util.List;

 import java.util.Set;

 public class Solution {

     private TrieNode root = new TrieNode();

     private int[] ro = {-1, 1, 0, 0};

     private int[] co = {0, 0, -1, 1};

     private void find(char[][] board, boolean[][] visited, int row, int col, TrieNode node, Set<String> founded) {

         visited[row][col] = true;

         TrieNode current = node.nexts[board[row][col]-'a'];

         if (current.word != null) founded.add(current.word);

         for(int i=0; i<4; i++) {

             int nr = row + ro[i];

             int nc = col + co[i];

             if (nr < 0 || nr >= board.length || nc < 0 || nc >= board[nr].length || visited[nr][nc]) continue;

             TrieNode next = current.nexts[board[nr][nc]-'a'];

             if (next != null) find(board, visited, nr, nc, current, founded);

         }

         visited[row][col] = false;

     }

     public List<String> findWords(char[][] board, String[] words) {

         Set<String> founded = new HashSet<>();

         for(int i=0; i<words.length; i++) {

             char[] wa = words[i].toCharArray();

             TrieNode node = root;

             for(int j=0; j<wa.length; j++) node = node.append(wa[j]);

             node.word = words[i];

         }

         boolean[][] visited = new boolean[board.length][board[0].length];

         for(int i=0; i<board.length; i++) {

             for(int j=0; j<board[i].length; j++) {

                 if (root.nexts[board[i][j]-'a'] != null) find(board, visited, i, j, root, founded);

             }

         }

         List<String> results = new ArrayList<>();

         results.addAll(founded);

         return results;

     }

 }

 class TrieNode {

     String word;

     TrieNode[] nexts = new TrieNode[26];

     TrieNode append(char ch) {

         if (nexts[ch-'a'] != null) return nexts[ch-'a'];

         nexts[ch-'a'] = new TrieNode();

         return nexts[ch-'a'];

     }

 }

] = new TrieNode();
return nexts[ch-'a']; }}

巴特西

Leetcode 212.单词搜索II

单词搜索II

最新文章

热门文章