Given aboardwhich is a 2D matrix includesa-zand dictionarydict, find the largest collection of words on the board, the words can not overlap in the same position. return thesizeof largest collection.

Have you met this question in a real interview?

Yes

Example

Give a board below

[['a', 'b', 'c'],
 ['d', 'e', 'f'],
 ['g', 'h', 'i']]

dict =["abc", "cfi", "beh", "defi", "gh"]
Return3// we can get the largest collection["abc", "defi", "gh"]

 /**
  * 本代码由九章算法编辑提供。版权所有，转发请注明出处。
  * - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。
  * - 现有的面试培训课程包括：九章算法班，系统设计班，算法强化班，Java入门与基础算法班，Android 项目实战班，Big Data 项目实战班，
  * - 更多详情请见官方网站：http://www.jiuzhang.com/?source=code
  */ 

class Trie {
    TrieNode root;

    Trie() {
        root = new TrieNode('0');
    }

    public void insert(String word) {
        if(word == null || word.length() == 0) {
            return;
        }
        TrieNode node = root;
        for(int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            if(node.children[ch - 'a'] == null) {
                node.children[ch - 'a'] = new TrieNode(ch);
            }
            node = node.children[ch - 'a'];
        }
        node.isWord = true;
    }
}

class TrieNode {
    char value;
    boolean isWord;
    TrieNode[] children;

    TrieNode(char v) {
        value = v;
        isWord = false;
        children = new TrieNode[26];
    }
}

public class Solution {
    /**
     * @param board a list of lists of character
     * @param words a list of string
     * @return an integer
     */
    public int boggleGame(char[][] board, String[] words) {
        // Write your code here
        Trie trie = new Trie();
        for(String word : words) {
            trie.insert(word);
        }

        int m = board.length;
        int n = board[0].length;
        List<String> result = new ArrayList<>();
        boolean[][] visited = new boolean[m][n];
        List<String> path = new ArrayList<>();
        findWords(result, board, visited, path, 0, 0, trie.root);
        return result.size();
    }

    public void findWords(List<String> result, char[][] board, boolean[][] visited, List<String> words, int x, int y, TrieNode root) {

        int m = board.length;
        int n = board[0].length;
        for (int i = x; i < m; i++) {
            for (int j = y; j < n; j++) {
                List<List<Integer>> nextWordIndexes = new ArrayList<>();
                List<Integer> path = new ArrayList<>();
                getNextWords(nextWordIndexes, board, visited, path, i, j, root);
                for (List<Integer> indexes : nextWordIndexes) {
                    String word = "";
                    for (int index : indexes) {
                        int row = index / n;
                        int col = index % n;
                        visited[row][col] = true;
                        word += board[row][col];
                    }

                    words.add(word);
                    if (words.size() > result.size()) {
                        result.clear();
                        result.addAll(words);
                    }
                    findWords(result, board, visited, words, i, j, root);
                    for (int index : indexes) {
                        int row = index / n;
                        int col = index % n;
                        visited[row][col] = false;
                    }
                    words.remove(words.size() - 1);
                }
            }
            y = 0;
        }
    }

    int []dx = {0, 1, 0, -1};
    int []dy = {1, 0, -1, 0};
    private void getNextWords(List<List<Integer>> words, char[][] board,
                              boolean[][] visited, List<Integer> path, int i, int j, TrieNode root) {
        if(i < 0 | i >= board.length || j < 0 || j >= board[0].length
            || visited[i][j] == true || root.children[board[i][j] - 'a'] == null) {
            return;
        }

        root = root.children[board[i][j] - 'a'];
        if(root.isWord) {
            List<Integer> newPath = new ArrayList<>(path);
            newPath.add(i * board[0].length + j);
            words.add(newPath);
            return;
        }

        visited[i][j] = true;
        path.add(i * board[0].length + j);
        for (int k = 0; k < 4; k ++) {
            getNextWords(words, board, visited, path, i + dx[k], j + dy[k], root);
        }
        path.remove(path.size() - 1);
        visited[i][j] = false;
    }
}



C++



class TrieNode {
public:
    bool isWord;
    string word;
    TrieNode* next[26];
    TrieNode() {
        isWord = false;
        for (int i = 0; i < 26; ++i) {
            next[i] = NULL;
        }
    }
};



class Solution {
public:
    /**
     * @param board a list of lists of character
     * @param words a list of string
     * @return an integer
     */
    int boggleGame(vector<vector<char> > &board, vector<string> &words) {
        // write your code here
        if (board.empty() || board[0].empty()) {
            return 0;
        }
        int max = 0;
        TrieNode* root = new TrieNode();
        for (auto& word : words) {
            insertWord(word, root);
        }
        int n = board.size();
        int m = board[0].size();
        vector<vector<bool>> f(n, vector<bool>(m, false));

        vector<string> tmp;
        findWords(board, 0, 0, root, f, tmp, max);
        return max;
    }

    void findWords(vector<vector<char> > &board, int x, int y, TrieNode* root, vector<vector<bool>> &f, vector<string> &tmp, int& max) {
        int n = board.size();
        int m = board[0].size();
        for (int i = x; i < n; ++i) {
            for (int j = y; j < m; ++j) {
                vector<vector<Point>> paths;
                vector<Point> path;
                getNextPoints(board, i, j, f, root, paths, path);
                for (auto& pts : paths) {
                    string word;
                    for (auto& pt : pts) {
                        word += board[pt.x][pt.y];
                        f[pt.x][pt.y] = true;
                    }
                    tmp.push_back(word);
                    if (tmp.size() > max) {
                        max = tmp.size();
                    }
                    findWords(board, i, j, root, f, tmp, max);
                    for (auto& pt : pts) {
                        word += board[pt.x][pt.y];
                        f[pt.x][pt.y] = false;
                    }
                    tmp.pop_back();
                }
            }
            y = 0;
        }
    }

    void getNextPoints(vector<vector<char> > &board, int i, int j, vector<vector<bool>> &f, TrieNode* root, vector<vector<Point>>& paths, vector<Point> &path) {
        root = root->next[board[i][j] - 'a'];
        if (f[i][j] || root == NULL) {
            return;
        }
        f[i][j] = true;
        path.push_back(Point(i, j));
        if (root->isWord) {
            paths.push_back(path);
        } else {
            int dx[4] = {1, -1, 0, 0};
            int dy[4] = {0,  0, 1, -1};
            vector<vector<int>> offsets = {{1,0}, {-1,0}, {0,1}, {0,-1}};
            for (auto& offset : offsets) {
                int x = i + offset[0];
                int y = j + offset[1];
                if (IsInside(x, y, f.size(), f[0].size())) {
                    getNextPoints(board, x, y, f, root, paths, path);
                }
            }
        }
        path.pop_back();
        f[i][j] = false;
    }

    bool IsInside(int x, int y, int n, int m) {
        return x >= 0 && x < n && y >= 0 && y < m;
    }

    void insertWord(string& word, TrieNode* root) {
        TrieNode* p = root;
        for (char c : word) {
            if (p->next[c - 'a'] == NULL) {
                p->next[c - 'a'] = new TrieNode();
            }
            p = p->next[c - 'a'];
        }
        p->isWord = true;
        p->word = word;
    }
};