问题

直觉：因为我们必须通过上/下/左/右方式遍历来找到单词数组中存在的单词（在网格/板上）。
可以使用回溯来完成遍历
为了搜索单词，我们可以使用 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 (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 = 0 &amp;&amp; J &gt;= 0 &amp;&amp; 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 




          

            

            
        </string></string></string>

以上就是单词搜索 II的详细内容，更多请关注php中文网其它相关文章！