c++ 98% solution with Trie and backtracking


  • 0
    class TrieNode {
    public:
        TrieNode() : endOfWord(false) {
        	memset(children, 0, sizeof(children));
        }
    
        bool isLeaf() {
        	return endOfWord;
        }
    
        TrieNode* children[26];
        bool endOfWord;
    };
    
    class Trie {
    public:
        Trie() {
            root = new TrieNode();
        }
    
        TrieNode* getRoot() {
        	return root;
        }
    
        TrieNode* getTrieNodeForNextChar(TrieNode* cur, char next) {
        	if (!cur)
        		return NULL;
        	return cur->children[next - 'a'];
        }
    
        void insert(string word) {
        	TrieNode* cur = root;
            for (int i = 0; i < word.size(); i++) {
                if (!cur->children[word[i] - 'a'])
                    cur->children[word[i] - 'a'] = new TrieNode();
                cur = cur->children[word[i] - 'a'];
            }
            cur->endOfWord = true;
        }
    
    private:
        TrieNode* root;
    };
    
    void dfs(vector<vector<char>>& board, int m, int n, int i, int j, string& prefix, TrieNode* cur, Trie* dict, set<string>& ans) {
        if (i == -1 || i == m || j == -1 || j == n || board[i][j] == '#')
            return;
        cur = dict->getTrieNodeForNextChar(cur, board[i][j]);
        if (!cur)
            return;
        char curChar = board[i][j];
        prefix += curChar;
        board[i][j] = '#';
        if (cur->isLeaf())
            ans.insert(prefix);
        dfs(board, m, n, i-1, j, prefix, cur, dict, ans);
        dfs(board, m, n, i+1, j, prefix, cur, dict, ans);
        dfs(board, m, n, i, j-1, prefix, cur, dict, ans);
        dfs(board, m, n, i, j+1, prefix, cur, dict, ans);
        board[i][j] = curChar;
        prefix.pop_back();
    }
    
    // build a Trie, Do a dfs starting from each char on the board, and each search stops when the current sequence isn't
    // a prefix of any word in the trie
    // add to the return value whenever we reach a leaf in the trie
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        set<string> s;
        if (board.empty() || board[0].empty())
            return vector<string> {};
        Trie* dict = new Trie();
        for (auto w : words)
        	dict->insert(w);
    
        int m = board.size(), n = board[0].size();
        TrieNode* root = dict->getRoot();
        for (int i = 0; i < m; i++)
        	for (int j = 0; j < n; j++) {
        	    string prefix = "";
        	    dfs(board, m, n, i, j, prefix, root, dict, s);
        	}
        vector<string> ans(s.begin(), s.end());
        return ans;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.