解法

前缀树的使用，以及深度优先遍历，置位和取消置位

代码

import java.util.ArrayList;
import java.util.List;
import java.util.Collections;

class Solution {
   public static class TrieNode {
        String word;
        TrieNode[] node;

        public TrieNode() {
            node = new TrieNode[26];
            word="";
        }
    }
    public static class Trie {
        TrieNode root;

        public Trie() {
            root = new TrieNode();
        }

        public void insert(String word) {
            TrieNode cur = root;
            for (int i = 0; i < word.length(); i++) {
                int temp = word.charAt(i) - 'a';
                if (cur.node[temp] == null) {
                    cur.node[temp] = new TrieNode();
                }
                cur = cur.node[temp];
            }
            cur.word = word;
        }
    }
    public ArrayList<String> res=new ArrayList<>();
    public List<String> findWords(char[][] board, String[] words) {
        Trie tree=new Trie();
        for(int i=0;i<words.length;i++)
        {
            tree.insert(words[i]);
        }
        for(int i=0;i<board.length;i++)
            for(int j=0;j<board[0].length;j++)
            {
                dfs(board,i,j,tree.root);
            }
        Collections.sort(res);
        return res;
    }
    public void dfs(char[][] board,int i,int j,TrieNode node)
    {
        if (i > board.length - 1 || j > board[0].length - 1 || j < 0 || i < 0) return;
        if (board[i][j]=='#') return ;
        char cur=board[i][j];
        if(node.node[cur-'a']!=null){
            TrieNode curnode=node.node[cur-'a'];
            if(!curnode.word.equals(""))
            {
                res.add(curnode.word);
                curnode.word="";
            }
            board[i][j]='#';
            dfs(board,i+1,j,curnode);
            dfs(board,i-1,j,curnode);
            dfs(board,i,j+1,curnode);
            dfs(board,i,j-1,curnode);
            board[i][j]=cur;
        }else  return ;
    }
}