Graph: Given a dictionary and a matrix, find all the words from the dictionary found in matrix

Problem Statement:

You are given a dictionary[] and a character matrix.

You need to find all the words from the dictionary that can be formed in the board.

A word can be formed by starting from any cell and moving either in vertical or horizontal direction.

Each cell can be used at most only once while forming a word.

Example:

Input:

    vector<string> dictionary = {"PRO", "DEV"};

	vector<vector<char>> grid = {
    {'P', 'R', 'O'},
    {'R', 'B', 'E'},
    {'V', 'E', 'D'}
		};

Output:

["PRO","DEV"]

Solution Explanation:

We will solve the problem by using TRIE + DFS + Backtracking.

Insert all the words into Trie

Then perform DFS on all the cells of the board.

For each DFS call, check if the current character exist in the TRIE.

Then make the current cell as visited, if the word exist in the TRIE, so that it will not be used for other words.

Backtracking will restore the state after exploring a path

Time Complexity: O(1)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct TrieNode
{
    bool is_end;

    string word;

    TrieNode* child[26];

    TrieNode()
    {
        is_end = false;

        word = "";

        for(int i = 0; i < 26; i++)
        {
            child[i] = NULL;
        }
    }
};

TrieNode* root = new TrieNode();

void insert(string& str)
{
    int n = str.size();

    TrieNode* curr = root;

    for(int i = 0; i < n; i++)
    {
        int idx = str[i] - 'a';

        if(curr -> child[idx] == NULL)
        {
            curr -> child[idx] = new TrieNode();
        }

        curr = curr -> child[idx];
    }

    curr -> is_end = true;

    curr -> word = str;
}

vector<string> res;

vector<int> dx = {-1, 0, 1, 0};

vector<int> dy = {0, 1, 0, -1};

void dfs(vector<vector<char>>& grid, int i, int j, int n, int m, TrieNode* curr)
{
     
    if(i < 0 || i >= n || j < 0 || j >= m || grid[i][j] == '#')
    {
        return;
    }

    int idx = grid[i][j] - 'a';

    if(curr -> child[idx] == NULL)
    {
        return;
    }

    curr = curr -> child[idx];

    if(curr -> is_end)
    {
        res.push_back(curr -> word);
        curr -> is_end = false;
    }

    char val = grid[i][j];

    grid[i][j] = '#';

    for(int k = 0; k < 4; k++)
    {
        int new_i = i + dx[k];

        int new_j = j + dy[k];

        dfs(grid, new_i, new_j, n, m, curr);
    }

    grid[i][j] = val;
}

vector<string> solution(vector<vector<char>>& grid, vector<string>& words) 
{
    
    int n = grid.size();
    
    int m = grid[0].size();

    for(auto word : words)
    {
        insert(word);
    }

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            dfs(grid, i, j, n, m, root);
        }
    }

    return res;
}

int main()
{
    vector<string> dictionary = {"PRO", "DEV"};

	vector<vector<char>> grid = {
    {'P', 'R', 'O'},
    {'R', 'B', 'E'},
    {'V', 'E', 'D'}
		};


    vector<string> ans = solution(grid, dictionary);

    //sort(ans.begin(), ans.end());

    cout << "[";
    for (int i = 0; i < ans.size(); i++)
    {
        cout << "\"" << ans[i] << "\"";
        if (i != ans.size() - 1)
            cout << ",";
    }
    cout << "]";

    return 0;
}

Output

["PRO","DEV"]