Problem Statement

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example 1:

Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]

Problem Link

Word Search II - LeetCode

Reference Video

https://www.youtube.com/watch?v=EmvsBM7o-5k&ab_channel=TECHDOSE

Code

class Solution {
public:
    struct TrieNode {
        char ch;
        bool wordend;//denotes whether the word has ended at the current node or not
        string word;//stores the entire word at the node where wordend = true
        TrieNode *child[26];
        
        TrieNode(char c)
        {
            ch = c;
            wordend = false;
            word = "";
            for(int i=0;i<26;i++)
                child[i] = NULL;
        }
    };
    TrieNode *root = new TrieNode('/');
    void insert(string str)
    {
        TrieNode *curr = root;
        
        for(char ch:str)
        {
            int index = ch-'a';
            if(!curr->child[index])
                curr->child[index] = new TrieNode(ch);
            curr = curr->child[index];
        }
        curr->word = str;
        curr->wordend = true;
    }
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        
        
        int m = board.size();
        int n = board[0].size();
        vector<string> res;
        
        for(string word:words)
            insert(word);
        
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
                dfs(i,j,m,n,board,root,res);
        }
        
        return res;
        
    }
    
    void dfs(int i,int j,int m,int n,vector<vector<char>>& board,TrieNode *curr,vector<string> &res)
    {
        
        
        if(i<0 || j<0 || i>m-1 || j>n-1 || board[i][j]=='V')
            return;
        
        int index = board[i][j] - 'a';
        if(!curr->child[index])
            return;
        
        curr = curr->child[index];
        
        if(curr->wordend)
        {
            res.push_back(curr->word);
            **curr->wordend = false; //See video to understand this**
        }
        char t = board[i][j];
        board[i][j] = 'V';
        
        dfs(i+1,j,m,n,board,curr,res); 
        dfs(i,j+1,m,n,board,curr,res); 
        dfs(i-1,j,m,n,board,curr,res); 
        dfs(i,j-1,m,n,board,curr,res); 
       
        
        board[i][j] = t;
        
        
        
        
    }
};
static const int _=[](){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    return 0;
}();

// Time Complexity = O(mnmn)