LeetCode 212 Word Search II(Trieツリー＋DFS)

Given a 2D board and a list of words from the dictionary, find all words in the board.
Each word must be constructed from letters of sequentially adjacent cell, where "adjacent"cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.
For example, Given words =  ["oath","pea","eat","rain"]  and board =

[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

Return  ["eat","oath"]
.
Note:
You may assume that all inputs are consist of lowercase letters  a-z .
タイトルリンク:https://leetcode.com/problems/word-search-ii/
題目の分析:先に所定の単語によってTrie木を創立して、それから行列の中のすべての単語の頭文字から深く探して、深く探したのは辞書の木の中の単語の方向によって、1つを見つけた後に直接returnすることができなくて、ある単語が別の単語の接頭辞である可能性があるためです.
63%を破った

public class Solution {
    
    public static final int dx[] = {1, 0, -1, 0};
    public static final int dy[] = {0, 1, 0, -1};
    
    public boolean[][] vis;
    
    class Trie {
        boolean end;
        String word;
        Trie[] nxt;
        
        public Trie() {
            nxt = new Trie[26];
            end = false;
            word = "";
            for (int i = 0; i < 26; i ++) {
                nxt[i] = null;
            }
        }
        
        public void Insert(Trie root, String str) {
            int len = str.length();
            Trie p = root;
            for (int i = 0; i < len; i ++) {
                int idx = str.charAt(i) - 'a';
                if (p.nxt[idx] == null) {
                    p.nxt[idx] = new Trie();
                }
                p = p.nxt[idx];
            }
            p.end = true;
            p.word = str;
        }
    }
    
    public void DFS(int x, int y, int n, int m, Trie cur, boolean[][] vis, char[][] board, List ans) {
        if (cur == null) {
            return;
        }
        if (cur.end) {
            cur.end = false;
            ans.add(cur.word);
        }
        for (int i = 0; i < 4; i ++) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (xx >= 0 && yy >= 0 && xx < n && yy < m && !vis[xx][yy]) {
                int idx = board[xx][yy] - 'a';
                if (cur.nxt[idx] != null) {
                    vis[xx][yy] = true;
                    DFS(xx, yy, n, m, cur.nxt[idx], vis, board, ans);
                    vis[xx][yy] = false;
                }
            } 
        }
        return;
    }
    
    public List findWords(char[][] board, String[] words) {
        Trie root = new Trie();
        for (int i = 0; i < words.length; i ++) {
            root.Insert(root, words[i]);
        }
        List ans = new ArrayList<>();
        int n = board.length;
        if (n == 0) {
            return ans;
        }
        int m = board[0].length;
        vis = new boolean[n][m];
        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < m; j ++) {               
                int idx = board[i][j] - 'a';
                if (root.nxt[idx] != null) {
                    vis[i][j] = true;
                    DFS(i, j, n, m, root.nxt[idx], vis, board, ans);
                    vis[i][j] = false;
                }
            }
        }
        // Collections.sort(ans, new Comparator() {
        //     @Override
        //     public int compare(Object o1, Object o2) {
        //         return ((String) o1).compareTo((String) o2);
                
        //     }
        // });
        return ans;
    }
}