Word Search II(Hard)

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"].

解题思路：回溯+DFS+Trie

如果还像一中那样，对每个词进行一遍Word Search I， 那复杂度就太高了。 我们可以 先用待查单词建立一个字典树，这样我们在从矩阵中某个点开始深度优先搜索时，可以直接用字典树判断当前组成的字符串是否是某个单词的前缀。如果是某个单词的前缀，再继续搜索下去。字典树同样也提供search接口，所以同样可以用于判断是否已经搜索到这个词了。

public List<String> findWords(char[][] board, String[] words) {
    List<String> res = new ArrayList<>();

    int rows = board.length;
    int cols = board[0].length;
    boolean[][] visited = new boolean[rows][cols];

    Trie trie = new Trie();
    for(String word : words) {
        trie.insert(word);
    }

    for(int i=0;i<rows;i++)
        for(int j=0;j<cols;j++) {
            StringBuilder cur = new StringBuilder();
            helper(board,words,i,j,cur,visited,res,trie);
        }

    return res;
}

private void helper(char[][] board, String[] words, int row, int col,
                        StringBuilder current,boolean[][] visited,
                        List<String> res,Trie trie){
    int rows = board.length;
    int cols = board[0].length;

    if(row<0 || row >= rows || col<0 || col>=cols)
        return;

    if(visited[row][col])
        return;

    current.append(board[row][col]);
    visited[row][col] = true;
    String s = current.toString();

    //接用字典树判断当前组成的字符串是否是某个单词的前缀
    if(trie.startsWith(s)) {
        //如果字典树中存在该字符串，说明找到了单词
        if(trie.search(s))
            res.add(s);

        helper(board,words,row-1,col,current,visited,res,trie);
        helper(board,words,row+1,col,current,visited,res,trie);
        helper(board,words,row,col-1,current,visited,res,trie);
        helper(board,words,row,col+1,current,visited,res,trie);
    }

    current.deleteCharAt(current.length()-1);
    visited[row][col] = false;
}

Reference

1 Trie Implementation