Word Search II

题目
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.

答案
下面的代码省略的Trie的实现部分，以方便阅读

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

        // Insert all words into trie
        root = new TrieNode();
        for(int i = 0; i < words.length; i++) {
            insert(words[i]);
        }

        int rows = board.length, cols = board[0].length;
        boolean[][] visited = new boolean[rows][cols];
        // Do dfs starting with every single cell
        // If the dfs path does not match with trie, return immediately
        // if we see trie.leaf = true, add to list

        for(int i = 0; i < rows; i++) {
            for(int j = 0; j < cols; j++) {
                dfs(board, visited, i, j, root, "", list);
            }
        }
        return list;
    }

    public void dfs(char[][] board, boolean[][] visited, int i, int j, TrieNode curr, String word, List<String> list) {
        if(i < 0 || i >= board.length || j < 0 || j >= board[0].length || visited[i][j])
            return;
        char curr_c = board[i][j];
        curr = curr.children[curr_c - 'a'];
        if(curr == null) return;
        word = word + curr_c;
        if(curr.bLeaf && !curr.visited) {
            curr.visited = true;
            list.add(word);
        }

        visited[i][j] = true;
        dfs(board, visited, i - 1, j, curr, word, list);
        dfs(board, visited, i + 1, j, curr, word, list);
        dfs(board, visited, i, j - 1, curr, word, list);
        dfs(board, visited, i, j + 1, curr, word, list);
        visited[i][j] = false;
    }

完整AC答案

class Solution {
    class TrieNode {
        // Initialize your data structure here.
        public TrieNode() {
            children = new TrieNode[26];
            bLeaf = false;
        }
        int value;
        boolean bLeaf;
        boolean visited;
        TrieNode[] children;
    }

    private boolean charExist(char c, TrieNode curr) {
        return curr.children[c - 'a'] != null;
    }
    private TrieNode nextNode(char c, TrieNode curr) {
        return curr.children[c - 'a'];
    }
    private void insertChar(char c, TrieNode curr, TrieNode ins) {
        curr.children[c - 'a'] = ins;
    }


    TrieNode root;

    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode curr = root;
        for(int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if(!charExist(c, curr)) {
                TrieNode newnode = new TrieNode();
                newnode.value = c;
                insertChar(c, curr, newnode);
            }
            // You will need to mark this node as leaf, even if it is not really a leaf in the tree
            // but it is a leaf for this particular string word

            curr = nextNode(c, curr);
            if(i == word.length() - 1)
                curr.bLeaf = true;
        }
    }

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

        // Insert all words into trie
        root = new TrieNode();
        for(int i = 0; i < words.length; i++) {
            insert(words[i]);
        }

        int rows = board.length, cols = board[0].length;
        boolean[][] visited = new boolean[rows][cols];
        // Do dfs starting with every single cell
        // If the dfs path does not match with trie, return immediately
        // if we see trie.leaf = true, add to list

        for(int i = 0; i < rows; i++) {
            for(int j = 0; j < cols; j++) {
                dfs(board, visited, i, j, root, "", list);
            }
        }
        return list;
    }

    public void dfs(char[][] board, boolean[][] visited, int i, int j, TrieNode curr, String word, List<String> list) {
        if(i < 0 || i >= board.length || j < 0 || j >= board[0].length || visited[i][j])
            return;
        char curr_c = board[i][j];
        curr = curr.children[curr_c - 'a'];
        if(curr == null) return;
        word = word + curr_c;
        if(curr.bLeaf && !curr.visited) {
            curr.visited = true;
            list.add(word);
        }

        visited[i][j] = true;
        dfs(board, visited, i - 1, j, curr, word, list);
        dfs(board, visited, i + 1, j, curr, word, list);
        dfs(board, visited, i, j - 1, curr, word, list);
        dfs(board, visited, i, j + 1, curr, word, list);
        visited[i][j] = false;
    }
}