原题链接：

这道题目也是在看完 LeetCode 上实现前缀树的文章后推荐的练习题。这道题目初看毫无思路，官方也并未提供解答，还是只能看评论区别人提交的答案了。然后评分最高的就是使用前缀树+回溯法（Backtracking）来解决了：

import java.util.ArrayList;import java.util.Arrays;import java.util.List;/** * Created by clearbug on 2018/2/26. */public class Solution {    class TrieNode {        TrieNode[] next = new TrieNode[26];        String word;        char c;        @Override        public String toString() {            return "[c is: " + c + ", word is: " + word + "]";        }    }    public TrieNode buildTrie(String[] words) {        TrieNode root = new TrieNode();        for (String w : words) {            TrieNode p = root;            for (char c : w.toCharArray()) {                int i = c - 'a';                if (p.next[i] == null) {                    p.next[i] = new TrieNode();                    p.next[i].c = c;                }                p = p.next[i];            }            p.word = w;        }        return root;    }    public static void main(String[] args) {        char[][] board = {                {'o', 'a', 'a', 'n'},                {'e', 't', 'a', 'e'},                {'i', 'h', 'k', 'r'},                {'i', 'f', 'l', 'v'}        };        String[] words = {"oath", "pea", "eat", "rain"};        Solution s = new Solution();        System.out.println(s.findWords(board, words));;    }    public List
    
      findWords(char[][] board, String[] words) {        List
     
       res = new ArrayList<>();        TrieNode root = buildTrie(words);        for (int i = 0; i < board.length; i++) {            for (int j = 0; j < board[0].length; j++) {                dfs (board, i, j, root, res);            }        }        return res;    }    public void dfs(char[][] board, int i, int j, TrieNode p, List
      
        res) {//        print(board, i, j, p, res);        char c = board[i][j];        if (c == '#' || p.next[c - 'a'] == null) return;        p = p.next[c - 'a'];        if (p.word != null) {   // found one            res.add(p.word);            p.word = null;     // de-duplicate        }        board[i][j] = '#';        if (i > 0) dfs(board, i - 1, j ,p, res);        if (j > 0) dfs(board, i, j - 1, p, res);        if (i < board.length - 1) dfs(board, i + 1, j, p, res);        if (j < board[0].length - 1) dfs(board, i, j + 1, p, res);        board[i][j] = c;    }    public void print(char[][] board, int i, int j, TrieNode p, List
       
         res) {        System.out.println("====================================================");        System.out.println("board is: ");        for (int k = 0; k < board[0].length; k++) {            System.out.println(Arrays.toString(board[k]));        }        System.out.println("i is: " + i + ", j is: " + j);        System.out.println("p is: " + p);        System.out.println("res is: " + res);        System.out.println("====================================================");    }}
       
      
     
    

回溯法有点绕，所以看解答时不能死扣细节，而是看完代码后在脑子中形成大致思路！