Word search, trie and backtrack

The word search problem can be solved by using the backtrack. The word search II is based on word search I. For the solution of word search I, it is based on backtrack. See here for word search I.

Word Search II

It is based on the word search I. We can use exactly the same backtrack method in work search I. In order to search the words more efficiently, we can build a trie to save the words in a more efficient way. We can think Trie as a base 26 number system which can be used to compress bunch of words.

If the trie has the height of 10, it can used to represent 26¹⁰ different words, which is pretty powerful.

struct TrieNode {
    bool isWord;
    vector<TrieNode*> children;
    TrieNode(): isWord(false){
        children.assign(26, nullptr);
    }
};
class Trie{
    public:
    TrieNode* root;
    Trie(){
        root = new TrieNode();
    }
    void addWord(string word){
        auto curr = root;
        for (auto c: word){
            if (curr -> children[c - 'a'] == nullptr){
                curr -> children[c - 'a'] = new TrieNode();
            }
            curr = curr -> children[c - 'a'];
        }
        curr -> isWord = true;
    }
};
class Solution {
public:
    vector<vector<char>> board;
    void backtrack(int i, int j, vector<string> & ret, string & hist, TrieNode* trie){
        const int n = board.size(), m = board[0].size();
        if (i < 0 || i >= n || j <0 || j >= m || board[i][j] == '#' || trie->children[board[i][j] - 'a'] == nullptr)return;
        char originalVal = board[i][j];
        hist.push_back(originalVal);
       
        auto curr = trie->children[board[i][j] - 'a'];
        if (curr -> isWord){
            ret.push_back(hist);
        }
        board[i][j] = '#';
        backtrack(i+1, j, ret, hist, curr);
        backtrack(i-1, j, ret, hist, curr);
        backtrack(i, j+1, ret, hist, curr);
        backtrack(i, j-1, ret, hist, curr);
        board[i][j] = originalVal;
        hist.pop_back();
        return;
    }
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        this -> board = board;
        Trie trie;
        for (auto word: words)trie.addWord(word);
        vector<string> ret;
        const int n = board.size(), m = board[0].size();
        for (int i = 0; i < n;++i){
            for (int j = 0; j < m; ++j){
                string hist = "";
                backtrack(i, j, ret, hist, trie.root);
            }
        }
        sort(ret.begin(), ret.end());
        ret.erase(unique(ret.begin(), ret.end()), ret.end());
        return ret;
    }
   
};

Time complexity

A rough time complexity should be

O(n²* 3^L) where L is the maximum length of the word.

In the worst case for this probem, it is

12^2*3^10 = 8503056

Which is doable.