Word Search II

Given a matrix of lower alphabets and a dictionary. Find all words in the dictionary that can be found in the matrix. A word can start from any position in the matrix and go left/right/up/down to the adjacent position. 

Example

Given matrix:

doafagaidcan

and dictionary:

{"dog", "dad", "dgdg", "can", "again"}

return {"dog", "dad", "can", "again"}

dog:

doafagaidcan

dad:

doafagaidcan

can:

doafagaidcan

again:

doafagaidcan

Challenge

Using trie to implement your algorithm.

 
struct TrieNode {
    bool  isEnd;
    TrieNode *children[26];
    
    TrieNode()
    {
        isEnd = false;
        memset(children, 0, sizeof(children));
    }
    
    void Add(string s, int index) {
        if (index == s.length()) {
            isEnd = true;
            return;
        } 
        
        if (children[s[index] - 'a'] == NULL)
            children[s[index] - 'a'] = new TrieNode();
        
        children[s[index]-'a']->Add(s, index+1); 
    }
    
    ~TrieNode() {
        for(int i = 0; i < 26; i++) {
            delete children[i];
        }
    }
};


class Solution {
public:
    /**
     * @param board: A list of lists of character
     * @param words: A list of string
     * @return: A list of string
     */
    vector<string> wordSearchII(vector<vector<char> > &board, vector<string> &words) {
        unordered_set<string>  ret;
        TrieNode trie; 
        for(int i = 0; i < words.size(); i++) 
            trie.Add(words[i],0);
        
        vector<vector<bool>> visited(board.size(), vector<bool>(board[0].size(), false));
        string temp;
        for(int i = 0; i < board.size(); i++)
            for(int j = 0; j< board[0].size(); j++) {
                helper(board, visited, &trie, i, j, temp,  ret); 
        }
        
        return vector<string>(ret.begin(), ret.end());
    }
    
    void helper(vector<vector<char>> &grid, 
            vector<vector<bool>> &visited,
            TrieNode *trie,
            int i,
            int j,
            string tmp,
           unordered_set<string> &ret)
    {

        if (!trie || i < 0 || i >= grid.size() || j < 0 || j >=grid[0].size())
             return;        
        if (!trie->children[grid[i][j]-'a'] || visited[i][j]) return;
        
        
        TrieNode *nextNode = trie->children[grid[i][j]-'a'];
        tmp.push_back(grid[i][j]);
        if (nextNode->isEnd)  ret.insert(tmp); 
        
        visited[i][j] = true;
        
        int x[] ={0, 0, -1, 1};
        int y[] ={-1,1, 0, 0};
        for(int k = 0; k < 4; k++) 
            helper(grid, visited, nextNode, i+x[k], j+ y[k], tmp, ret);  
            
        visited[i][j] = false; 
    } 
};