My code:

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

public class Solution {
    private class TrieNode {
        TrieNode[] next = new TrieNode[26];
        char val;
        boolean isWord;
        TrieNode(char val) {
            this.val = val;
        }
    }
    private TrieNode root = new TrieNode('r');
    int row = 0;
    int col = 0;
    private int[][] dir = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public List<String> findWords(char[][] board, String[] words) {
        List<String> ret = new ArrayList<String>();
        if (board == null || board.length == 0 || board[0].length == 0) {
            return ret;
        }
        
        row = board.length;
        col = board[0].length;
        buildTrie(words);
        boolean[][] mark = new boolean[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                dfs(i, j, mark, root, new StringBuilder(), ret, board);
            }
        }
        
        return ret;
    }
    
    private void dfs(int i, int j, boolean[][] mark, TrieNode root, StringBuilder path, List<String> ret, char[][] board) {
        int index = (int) (board[i][j] - 'a');
        if (root.next[index] == null) { // not match
            return;
        }
        
        int len = path.length();
        path.append(board[i][j]);
        mark[i][j] = true;
        
        TrieNode curr = root.next[index];
        if (curr.isWord) {
            ret.add(path.toString());
            curr.isWord = false; // cannot be found again
        }
        
        for (int k = 0; k < dir.length; k++) {
            int next_r = i + dir[k][0];
            int next_c = j + dir[k][1];
            if (isValid(next_r, next_c) && !mark[next_r][next_c]) {
                dfs(next_r, next_c, mark, curr, path, ret, board);
            }
        }
        path.setLength(len);
        mark[i][j] = false;
    }
    
    private boolean isValid(int i, int j) {
        if (i < 0 || i >= row) {
            return false;
        }
        else if (j < 0 || j>= col) {
            return false;
        }
        else {
            return true;
        }
    }
    
    private void buildTrie(String[] words) {
        for (String word : words) {
            buildTrie(word, 0, root);
        }    
    }
    
    private void buildTrie(String s, int index, TrieNode root) {
        if (index >= s.length()) {
            root.isWord = true;
            return;
        }
        int offset = (int) (s.charAt(index) - 'a');
        if (root.next[offset] == null) {
            root.next[offset] = new TrieNode(s.charAt(index));
        }
        TrieNode curr = root.next[offset];
        buildTrie(s, index + 1, curr);
    }
    
    public static void main(String[] args) {
        Solution test = new Solution();
        char[][] board = new char[][]{{'o','a','a','n'}, {'e','t','a','e'}, {'i','h','k','r'}, {'i','f','l','v'}};
        String[] words = new String[]{"oath","pea","eat","rain"};
        List<String> ret = test.findWords(board, words);
        System.out.println(ret.toString());
    }
    
}

reference:
https://discuss.leetcode.com/topic/33246/java-15ms-easiest-solution-100-00

這道題目沒能做出來，但真的很有意思。也給做難題提供了一些思路。
什么思路？當你對一道題目無從下手的時候，是為什么？
難道你真的一點都不會做嗎？一個解法都沒有嗎？
不是。你有你的暴力解法，但是覺得復雜度太高，太可笑了。不可能是最優(yōu)解。
當然不是最優(yōu)解。但大多數(shù)最優(yōu)解都不可能一下子想到的。
大多數(shù)最優(yōu)解都是從 brute-force 優(yōu)化出來的。
這道題目也是。
我當時在想，如果把 word search I 作為子函數(shù)，把輸入的string都過一遍，不就完事了嗎？但我沒有這么寫。為什么？
因為我知道太蠢了，過不了測試的。
那為什么過不了測試？
因為復雜度太高。
為什么復雜度高？
因為每個string都得做一次搜索操作，其實很多string有相同的prefix,可以放在一起搜索。也可以及時的截止
也就是說，我們在搜索 board[][]的時候，不是像 I 里面一樣，盲目的瞎搜索，而是得按照 words[] 定義的路徑去搜索。這樣，
才能更快地找到目標string
才能更快地發(fā)現(xiàn)，繼續(xù)下去，已經(jīng)不可能有word 與他匹配。
注意這里，如果用普通的搜索，當我們到達一個結點，判斷是否可以繼續(xù)dfs的時候，需要遍歷words[],看看是否有匹配的。復雜度就是
O(n), 每次搜索都是如此，復雜度驚人。所以，我們需要O(1)

那么我們的目標就是：
1 . 有方向性的去搜索
2 . 知道當前的character是否有匹配的word,要求操作是 瞬時的

再總結：
就是，我們需要知道，何時，已經(jīng)沒必要，再繼續(xù)dfs了，瞬時。

Trie 一定是最好的結構。

下面再來思考下 backtracking

有兩種形式

mark[i][j] = true;
int len = path.length();
path.append(curr);
for (int i = 0; i < n; i++) {
    if (!mark[m][n]) {
        dfs(...);
    }
}
mark[i][j] = false;
path.setLength(len);

上面這種形式，特征是，這一層，只干這一層的事。
可以看到， mark 標志位，改變string，都是這一層自己干的事。
唯一和下一層有關的。就是dfs的時候判斷下，他們是否已經(jīng)被訪問過了。

還有種形式

for (int i = begin; i < n; i++) {
    s += s.substring(begin, i + 1);
    group.add(s);
    dfs(i, s, group);
    group.remove(group.size() - 1);
}

這種的話，會將 backtacking 的過程在 for-loop里面實現(xiàn)。
之前的是在 for-loop 外面實現(xiàn)。
兩種不同的形式。

Anyway, Good luck, Richardo! -- 09/20/2016