Find the maximum number of times a word appears in a 2D-matrix-CodePudding

A 2-D grid of characters is given. For e.g. A 5x4 matrix is as follows :

{{'M','O','B','S','N'},
{'M','O','I','L','E'},
{'M','B','I','L','E'},
{'O','B','I','L','E'}}.

I have to find how many times the word "MOBILE" occurs in above grid using Java. For above the answer would be 3. I can traverse only in 4 directions, i.e. right, left, up, down. (NOT DIAGONALLY).

Another example :

                   {{'c','a','r'},
                   {'a','r','c'},
                   {'c','r','a'}}

and the word is "car". Answer for this grid would be 5.

I am aware of the fact that backtracking would help but HOW?

CodePudding user response：

If matrix has N elements, search string is k chars, there are m copies in matrix:

First, find all positions of first letter of string in matrix. O(N)

Then for each found position, do 4-way scan for n-1 characters. O(k*m)

Finally, sum all search results. O(m)

CodePudding user response：

Following is the solution to my own question. It took me a while to figure out. P.S. I've developed the solution ignoring any possibility of pallindromes.

import java.util.*;

class WOG{

static int m = 0;
static int n = 0;
static int[] x = {0,-1,0,1};
static int[] y = {-1,0,1,0};

public static int func(char[][] grid, int row, int col, String word, int k){

int occ = 0;

if(row>=m || row<0 || col<0 || col>=n)
    return 0;

if(grid[row][col]!=word.charAt(k))
    return 0;
    
if(k==word.length()-1)
    return 1;

for(int dir=0;dir<4;dir  ){
    
    int rd = row x[dir];
    int cd = col y[dir];
    
    occ  = func(grid,rd,cd,word,k 1);
}

return occ;

}

public static int pattern(char[][] grid, String word){

int res = 0;

for(int i=0;i<m;i  ){
    for(int j=0;j<n;j  ){
        res  = func(grid,i,j,word,0);
    }
}

return res;

}

public static void main(String[] args){
    
    char[][] grid2 = {{'m','o','b','s','n'},
              {'m','o','i','l','e'},
              {'m','b','i','l','e'},
              {'o','b','i','l','e'}};

    char[][] grid = {{'c','a','r'},
             {'a','r','c'},
             {'c','r','a'}};

    m = 4;
    n = 5;
    int ans = pattern(grid2,"mobile");
    System.out.println(ans);
}
}

I've made use of recursion and backtracking.