Strings: Count the number of string in 2D character array

Problem Statement:

You are given a string and a 2D char array.

You need to count the number of times the string is there in the 2D array.

The individual character can be present left to right, right to left, top to down or down to top.

Example

Input : a = {
            {B,B,H,B,B,B},
            {O,B,E,B,B,B},
            {L,B,L,B,B,B},
            {L,B,L,B,B,B},
            {E,B,O,B,B,B},
            {H,O,L,L,E,H}
            }
        str= "HELLO"

Output :3

Solution

The solution is very simple:

Below are the steps:

1. Start with the string by taking one character at a time and traverse the matrix.

2. Then search the character in the matrix in all the four directions recursively.

3. If a string is found, increase the count.

4. Once the search for one character is completed, repeat the same process for next character.

5. The final count will be the answer.

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <unordered_map>
#include <vector>
#include <sstream> 

using namespace std;

#define ARRAY_SIZE(a) (sizeof(a) / sizeof(*a))

int search_util_func(string word, int r, int c, string arr[], int maxRow, int maxCol, int index) 
{
   int count = 0;
   if (r >= 0 && r <= maxRow && c >= 0) 
   {
      if (c <= maxCol && word[index] == arr[r][c]) 
      {
         char res = word[index];
         index = index + 1;
         arr[r][c] = 0;
         if (word[index] == 0) 
         {
            count = 1;
         } else {
            count = count + search_util_func(word, r, c + 1, arr, maxRow, maxCol, index);
            count = count + search_util_func(word, r, c - 1, arr, maxRow, maxCol, index);
            count = count + search_util_func(word, r + 1, c, arr, maxRow, maxCol, index);
            count = count + search_util_func(word, r - 1, c, arr, maxRow, maxCol, index);
         }
         arr[r][c] = res;
      }
   }
   return count;
}

int find_string_count(string word, int r, int c, string str[], int countRow, int countCol) {
   int count = 0;
   for (int i = 0; i < countRow; ++i) 
   {
      for (int j = 0; j < countCol; ++j) 
      {
         count = count + search_util_func(word, i, j, str, countRow - 1, countCol - 1, 0);
      }
   }
   return count;
}

int main() 
{
      string word = "HELLO";
      string inp[] = {
            "BBHBBB",
            "OBEBBB",
            "LBLBBB",
            "LBLBBB",
            "EBOBBB",
            "HOLLEH"
            };

       string str[ARRAY_SIZE(inp)];  

       for (int i = 0; i < ARRAY_SIZE(inp); ++i)  
       {  
           str[i] = inp[i];  
       }  
  

         cout << "Count of number of given string in 2D character array: " << find_string_count(word, 0, 0, str, (sizeof(inp) / sizeof( * inp)), str[0].size());
         return 0;
}

Output:

Count of number of given string in 2D character array: 4