Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach
3.1.
Algorithm
4.
Dry Run
5.
Code
5.1.
Output
6.
Time and Space Complexities
6.1.
Time Complexity
6.2.
Space Complexity
7.
Frequently Asked Questions
7.1.
What is a string array?
7.2.
How to find all possible words in a board of characters?
7.3.
What is an edge?
7.4.
Which data structure is used for DFS traversal?
7.5.
What is the time complexity of DFS traversal?
8.
Conclusion
Last Updated: Mar 27, 2024
Easy

Find All Possible Words in a Board of Characters

Author Sneha Mallik
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

A fixed number of strings make up a string array. A string is a collection of a sequence of characters. These characters are stored in adjacent memory locations.

We will be using DFS Algorithm(Depth First Search), which is used to search or traverse a graph or tree data structure. DFS is generally used for solving puzzles.

To find all possible words in a board of characters

In this blog, we will discuss a simple DSA problem that can be categorized as a puzzle-based problem: To find all possible words in a board of characters.

Problem Statement

Given a dictionary, a method for looking up words in the dictionary, and a M x N board with one character in each cell. The goal is to identify every possible word that can be made from a group of adjacent characters. 

Problem Statement

We have to then return all words on the M x N board of characters and a list of strings “words”. Each word must be made up of letters from sequentially adjacent cells that are either horizontally or vertically neighbouring. The same letter cell may only be used once in a word.

We can move to any of the eight adjacent characters, but a word cannot have multiple instances of the same cell.

Example 1

Input

dictionary[] = ["HIRE", "PAY", "AIR", "WALL"]

board[] = [ ["H","I","T","N"], ["A","R","I","A"], ["J","E","K","R"], ["I","F","L","V"] ] 

Output

["AIR", "HIRE"]
 

Example 2

Input

dictionary[] = ["MNON"]

board[] = [["M","N"],["O","P"]] 

Output

[]

Approach

Let us discuss the approach for the given problem statement:

  • The idea is to take each character as a starting character and look for all words that begin with it. 
     
  • Depth First Traversal can find all words that begin with a specific character. We perform depth first search traversal from each cell. 
     
  • We keep track of which cells are visited so that each cell is only considered once in a word.

Algorithm

  • We will do a DFS search with backtracking for every word present.
     
  • We must begin with each character in the matrix and recursively explore all eight paths to see if they lead to a solution. 
     
  • We have to keep track of cells involved in the current path in the matrix to ensure that a word does not have multiple instances of the same cell. 
     
  • Before exploring any cell, ignore the cell if it is already covered in the current path.
     
  • We can use an array to store the relative position of movement from any cell to find all possible movements from that cell. 
     
  • For example, if the current cell is (m, n), we can use the following array to move to (m + row[k], n + col[k]) for 0 <= k <= 7.
    • short int directions[8][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {-1, -1}, {-1, 1}, {1, -1}};

Dry Run

Let's now discuss working through an example, and then we will code it: 

We will consider a dictionary having 4 words: ["HIRE","PAY","AIR","WALL"]

Dictionary containing strings

We have a board having characters in each cell.

Board having characters

The basic idea here we consider is to take every character as a starting character and search all words for it. 

First, we will look up words having starting letter ‘A’ in the dictionary as the above characters are indexed according to the alphabetical order of the characters, like 0 for A1 for B2 for C, and so on. 

DFS Step 1

After finding out character ‘A’, we will search for ‘I’ in all eight possible directions, i.e., North, West, South, East, North-East, North-West, South-East, South-West, but a word should not have multiple instances of the same cell. 

Similarly, we will look for ‘R’.

Step 2

Hence, we got our first word stored as “AIR”. 

The next character to find is ‘H’ on the board, which is according to the dictionary. We will then search for the first word, “HIRE”.

Step 3

After finding out character ‘H’, we will search for ‘I’ in all eight possible directions.

Similarly, we will look for ‘R’ and ‘E’.

Step 4

Hence, we got our second word stored as “HIRE”. 

Similarly, we will look for ‘P’ on the board. But since ‘P’ is not present, we won’t search for the further characters of the word ‘PAY’. Also, ‘W’ is not present, we won’t search for the further characters of the word ‘WALL’.

Therefore, we will get the following printed as output:

[“AIR”, “HIRE”] 

Code

// C++ program to find all possible words in a board of characters

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool dfs_on_grid(int i, int j, int match, string &target, vector<vector<char>> &board){
        int rows = board.size(), cols = board[0].size();
        if (match == target.size())
            return true;
        char original = board[i][j];
        board[i][j] = ';';
        short int directions[8][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {-1, -1}, {-1, 1}, {1, -1}};
        for (int k = 0; k < 8; k++){
            int dx = i + directions[k][0];
            int dy = j + directions[k][1];
            if (dx == rows or dy == cols or dx < 0 or dy < 0 or board[dx][dy] == ';')
                continue;
            if(board[dx][dy] != target[match])
                continue;
            if(dfs_on_grid(dx, dy, match + 1, target, board)){
                board[i][j] = original;
                return true;
            }
        }
        board[i][j] = original;
        return false;
    }
    
    vector<string> findWords(vector<vector<char> >& board, vector<string>& dictionary) {
    int rows = board.size(), cols = board[0].size();
    set<string> wordsSet;
    for(auto word : dictionary){
        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                if(board[i][j] != word[0])
                    continue;
                if(!dfs_on_grid(i, j, 1, word, board))
                    continue; 
                wordsSet.insert(word);
            }
        }
    }
    vector<string> words;
    for(auto it : wordsSet)
        words.push_back(it);
    return words;
}
};

// Driver Code 
int main() {
    int t;
    cout << "Enter number of dictionary:"<< endl;
    cin >> t;
    while (t--) {
        int N;
        cout << "Enter number of words in the dictionary:"<< endl;
        cin >> N;
        cout << "Enter words in the dictionary:"<< endl;
        vector<string> dictionary;
        for (int i = 0; i < N; ++i) {
            string s;
            cin >> s;
            dictionary.push_back(s);
        }
        
        int R, C;
        cout << "Enter row and column size:"<< endl;
        cin >> R >> C;
        
        cout << "Enter letters for each cell in "<< R <<" x "<< C <<" board:"<< endl;
        vector<vector<char> > board(R);
        for (int i = 0; i < R; i++) {
            board[i].resize(C);
            for (int j = 0; j < C; j++) cin >> board[i][j];
        }
        cout << "Output Generated:"<< endl;
        Solution obj;
        vector<string> output = obj.findWords(board, dictionary);
        if (output.size() == 0)
            cout << "-1";
        else {
            sort(output.begin(), output.end());
            for (int i = 0; i < output.size(); i++) cout << output[i] << " ";
        }
        cout << endl;
    }
}
You can also try this code with Online C++ Compiler
Run Code

Output

Output of Code

Time and Space Complexities

Let us discuss the time and space complexity for the problem: To find all possible words in a board of characters.

Time Complexity

Time Complexity

Time Complexity: O((N x W) + (R x C)2)

Here, ‘N’ is the number of strings/words taken in the dictionary.

‘W’ is the length of words, ‘R’ stands for Row size, and ‘C’ stands for Column size.

Space Complexity

Space Complexity

The function findWords() in the code takes a dictionary of “N” strings separated by space as input. This function also returns a list of words that is present on the board in lexicographical order.

Auxiliary Space: O((N x W) + (R x C))

Here, ‘N’ is the number of strings/words taken in the dictionary.

‘W’ is the length of words, ‘R’ stands for Row size, and ‘C’ stands for Column size.
 

Note: To avoid the printing of a word multiple times, we can use hashing approach. This approach will be helpful in keeping track of words being printed.

 

Check out this problem - Longest Common Prefix

Frequently Asked Questions

What is a string array?

A string array is an array with a fixed number of strings. 

How to find all possible words in a board of characters?

We must begin with each character in the matrix and recursively explore all eight paths to see if they lead to a solution. Depth First Traversal can find all words that begin with a specific character. We perform depth-first search traversal from each cell. 

We keep track of which cells are visited so that each cell is only considered once in a word. 

What is an edge?

Two cells are said to be connected by an edge if they share a common side or a common edge. In a graph, nodes are connected by edges.

Which data structure is used for DFS traversal?

The stack data structure is used for DFS(Depth First Search) traversal.

What is the time complexity of DFS traversal?

The time complexity of DFS traversal is O(V+E). V and E are the numbers of vertex and edges.

Conclusion

In this article, we covered all about the DSA problem to find all possible words in a board of characters. We discussed the algorithm, code, and dry run, along with the time and space complexities for the problem to find all possible words in a board of characters.

If you would like to learn more about these problems, check out our related articles on-

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, JavaScript, System Design, DBMS, Java, etc. Enroll in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations. 

Happy Learning, Ninja!🥷✨

Live masterclass