Problem statement: Given an m*n “board” of characters and a list of strings “words”, return all the words present on the board. Each word that you look up on the board must be constructed from adjacent letters( vertical or horizontal neighboring cells), sequentially such that no letter is used more than once in a word. 

Note: Both the ‘board’ and the strings in ‘words’ contain lowercase alphabets only.

Examples:

Input:

words={“mom”,” elephant”,” bob”,” badam”,” glad”}

Output: [“mom”,” badam”,” glad”]

Explanation: In the grid, you are able to find the 
words “badam”, “glad”, and “mom”. Hence the answer.

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Intuition: Whenever an array of strings, here it is ‘words’, is given, and then you are expected to find all possible words in a grid or if you are given any other similar kind of situation wherein a dictionary is involved, then it means you have to use trie data structure. This will be even more clear if you watch the 7 video lectures of the trie playlist by striver. 

Approach: 

The approach is very straightforward. After getting familiarized with trie data structure after you watch the above playlist, you will find implementing a trie, a very easy task. Hence let’s discuss the extra logic that comes into the picture here. 

After you insert all the words into the trie, start doing a DFS at each position in the grid, standing at the root of the trie. At each step, check whether there exists a node attached to the alphabet corresponding to the one present in the grid. If yes, proceed to that particular node and in the grid, go to that particular alphabet cell. At each step, check whether the flag of that node is set to true or not. If it is true, then you know that you have reached the end of that particular word of the ‘words’ array. String ‘s’ will keep track of this string and it will be inserted into your ‘ans’ array. Array simply refers to vector, the dynamic array in C++. 

This solution also employs a backtracking technique because you make a cell ‘*’ once you go to that so that the same character doesn’t repeat in the same word again and this change has to be reverted back once we have checked for that word so that you are not missing out on finding other words that are possibly associated with these changed characters. Also, it is not a good practice to modify the given input array when it’s passed by address.

Here, 

• search() of trie does DFS search.
• insert(word) of trie inserts word into the trie.
• put(ch, temp) will link the ch of the ‘links’ array to a new node temp.
• containsKey(ch) tells whether there is a node associated with that ch in that node or not. 
• get(ch) will return the node linked to ch.
• findWords() our leetcode function will call the search function of trie to make a DFS in that particular cell. 

Code:

struct Node{
    bool flag=false;
    Node* links[26];
    Node* get(char ch){
        return links[ch-'a'];
    }
    void put(char ch,Node* temp){
        links[ch-'a']=temp;
    }
    bool containsKey(char ch){
        return links[ch-'a']!=NULL;
    }
};

class Trie{
    public: Node* root;
    Trie(){
        root=new Node();
    }
    
    void insert(string s){
        Node* temp=root;
        for(int i=0;i<s.length();i++){
            if(!temp->containsKey(s[i]))
                temp->put(s[i],new Node());
            temp=temp->get(s[i]);
        }
        temp->flag=true;
    }
    
    void search(vector<vector<char>> &board, Node* temp,int i,int j,vector<string>
    &ans,string s){
	//temp is the current node in the trie.
	// (i,j) is the current cell in the grid.
        if(i<0 || j<0 || i==board.size() || j==board[0].size() || !temp || 
        board[i][j]=='*' || !temp->containsKey(board[i][j])) return;
        s+=board[i][j];
        Node* t=temp->get(board[i][j]);
        if(t->flag){
            ans.push_back(s);
            t->flag=false;
        }
        char ch=board[i][j];
        board[i][j] = '*'; //preventing this from getting reconsidered in same word
        search(board,temp->get(ch),i+1,j,ans,s); //bottom cell
        search(board,temp->get(ch),i,j+1,ans,s); //right cell
        search(board,temp->get(ch),i-1,j,ans,s); // top cell
        search(board,temp->get(ch),i,j-1,ans,s); //left cell
        board[i][j]=ch; //restoring original character
    }
};

class Solution {
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        Trie trie;
        for(string s:words) trie.insert(s);
        vector<string> ans;
        for(int i=0;i<board.size();i++)
            for(int j=0;j<board[0].size();j++)
                trie.search(board,trie.root,i,j,ans,"");
        return ans;
    }
};

Special thanks to Yashas Kamath for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article. If you want to suggest any improvement/correction in this article please mail us at [email protected]