Boggle Game, C++ (gcc)

Boggle Game

/* 24 Boggle Game
Given 2d matrix of letters, and a word dictionary, find a path which has largest number of words (existed inside the dictionary).
Leetcode #79 word Search I 
Leetcode #212 Word Search II
*/
#include <vector>
#include <iostream>
using namespace std;

struct TrieNode{
    string word; 
    vector<TrieNode*> next; 
    TrieNode(): word("") {
        next = vector<TrieNode*>(26, NULL); 
    }
};

TrieNode* buildTrie(vector<string>& words){
    TrieNode* root = new TrieNode();
    for(auto w: words) {
        TrieNode* p = root;   // insert each word
        for(auto c: w) {
            if(p->next[c-'a'] == NULL )
                p->next[c-'a'] = new TrieNode(); 
            p = p->next[c-'a'];
        }
        p->word = w; 
    }
    return root; 
}

class Solution{
public: 
    vector<string> search(vector<vector<char>>& board, vector<string> words){
        vector<string> res; 
        int m = board.size();  
        if(m==0) return res; 
        int n = board[0].size(); 
        
        TrieNode* root = buildTrie(words); 
        for(int i=0; i<m; i++) {
            for(int j=0; j<n; j++) {
                vector<string> v; // interim solution 
                dfs(res, v, board, i, j, root, root); 
            }
        }
        return res; 
    }
    
    void dfs(vector<string>& res, vector<string>& v, vector<vector<char>>& board, int i, int j, TrieNode* root, TrieNode* orig){
        if(root->word!=""){
            v.push_back(root->word);    //root->word =""; // cannot do this 
            if(v.size()>res.size()) {
                res = v; 
                cout << "v =";
                for(auto x: v) cout << x << "," ;
                cout << endl;
            }
            root = orig; // starting next letter
            // return; // continue searching, don't return 
        }
        if(i<0 || j<0 || i>=board.size() || j>=board[0].size()) return;
        
        char c = board[i][j];
        if(c=='#' || root->next[c-'a'] == NULL) return;
        
        board[i][j] = '#'; 
        vector<string> tmp = v;
        int dir[4][2]  = {{-1,0}, {1,0}, {0,-1}, {0,1}}; 
        for(int k=0; k<4; k++){
            dfs(res, v, board, i+dir[k][0], j+dir[k][1], root->next[c-'a'], orig); 
            v = tmp;
        }
        board[i][j] = c;  
    }

};

int main() {
    vector<vector<char>> board  = 
    {{'a', 'b', 'c'}, 
     {'d', 'e', 'f'}, 
     {'g', 'h', 'a'}}; 
    vector<string> words = {"ab", "eh", "af", "c", "ad","g"}; 
    Solution s; 
    vector<string> res = s.search(board, words); 
    for(auto s: res)
        cout << s << "-> ";
    cout << endl;
    return 0; 
}


run \| edit \| history \| help	0