单词搜索 II

问题

直觉:因为我们必须通过上/下/左/右的方式找到单词数组中存在的单词(在网格/板上)。 可以用回溯来完成遍历 我们可以使用搜索单词 trie，因为这也可以通过检查树上是否有前缀来帮助我们早期识别。这是为了避免不必要的遍历板（即，如果前缀不存在于特里树中，则使用前缀的字符串或单词形式不会出现在特里树中）

方法：我们将所有单词[]放入trie树中，然后遍历棋盘中的每个单元格(i,j)，在所有四个方向上形成各种字符串，然后在所有列表中 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的详细信息，请关注图灵教育的其他相关文章！