Pattern searching in 2d grid

Question

This is an interview question which i am trying to solve. You are given a 2D array of characters and a character pattern. WAP to find if pattern is present in 2D array. Pattern can be in any way (all 8 neighbors to be considered) but you can’t use same character twice while matching. Determine whether pattern is present or not

eg :

Matrix

{'A','C','P','R','C'}, 
{'X','S','O','P','C'}, 
{'V','O','V','N','I'}, 
{'W','G','F','M','N'}, 
{'Q','A','T','I','T'} 

And pattern is MICROSOFT.

the solution that i wrote is following.

    package junk;

import java.util.HashMap;

// Correct Implementation, probably.. :P
public class GridMatch {
    static int pInd = 0;           // current index on pattern, ie pattern.charAt(pInd) is to be searched next.
    static HashMap<String, Integer> hm=null;
    static int delta_i[]={ -1, -1, -1, 0, 0, 1, 1, 1 };
    static int delta_j[]={ -1, 0, 1, -1, 1, -1, 0, 1 };
    static char[][] grid = {   { 'A', 'C', 'P', 'R', 'C' }, 
                               { 'X', 'S', 'O', 'P', 'C' },
                               { 'V', 'O', 'V', 'N', 'I' },
                               { 'W', 'G', 'F', 'M', 'N' },
                               { 'Q', 'A', 'T', 'I', 'T' } };



    static HashMap<String, Integer> createMap(String s){
        HashMap<String, Integer> hm = new HashMap<String, Integer>();
        for(int i=0;i<s.length();i++){
            if(hm.get(String.valueOf(s.charAt(i))) != null)
                hm.put(String.valueOf(s.charAt(i)), hm.get(String.valueOf(s.charAt(i)))+1);
            else{
                hm.put(String.valueOf(s.charAt(i)), 1);
            }
        }
        return hm;
    }

    static boolean isAllowed(int row, int col){
         if (row >= grid.length || row < 0 || col >= grid[0].length || col < 0)
             return false;
         else return true;
    }

    static boolean searchGrid(int row, int col, String pat, boolean[][] visited, int pInd){

        // this char matched now remove one occurrence of it, mark relevant cell visited and move on to the next char in pattern .
        if (hm.get(String.valueOf(grid[row][col])) > 1)
            hm.put(String.valueOf(grid[row][col]), hm.get(String.valueOf(grid[row][col])) - 1);
        else
            hm.remove(String.valueOf(grid[row][col]));

        visited[row][col] = true;
        pInd++;
        if(hm.size()==0) // every character matched for this recursion stack
            return true; 

        for(int dir=0;dir<8;dir++){
            int k=0; int row_i = row+delta_i[dir]; int col_j = col+delta_j[dir];
            if(!isAllowed(row_i, col_j) || visited[row_i][col_j])
                continue;
            String currChar = String.valueOf(grid[row_i][col_j]);
            // if currChar is present, check recursively further
                if (grid[row_i][col_j] == pat.charAt(pInd)) { 
                    if (searchGrid(row_i, col_j, pat, visited,pInd))
                        return true;
                }
        }
// backtracking visited, pInd and hm's state by adding removed char and by default return false, 
        visited[row][col] = false;
        pInd--;
        if (hm.get(String.valueOf(grid[row][col])) !=null)
            hm.put(String.valueOf(grid[row][col]), hm.get(String.valueOf(grid[row][col])) + 1);
        else
            hm.put(String.valueOf(grid[row][col]),1);
        return false;
    }



    public static void main(String[] args) {
        int count=0;
        String pattern = "MICROSOFT";
//      String pattern = "Oa";
         hm = createMap(pattern);
         boolean[][] visited = new boolean[grid.length][grid[0].length];
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                count++;
                if(grid[i][j]==pattern.charAt(pInd))
                    if(searchGrid(i,j,pattern,visited,pInd)){
                        System.out.println("Present");
                        return;
                    }
            }
        }
        System.out.println("Not Present   "+count);

    }

}

I am using backtracking here so time complexity should be exponential but and not able to figure this out exactly. I feel it has polynomial running time = 8*T*P^2, where T is the number of chars in text grid, P is the number of chars in pattern string. Please comment on the code and its complexity, also suggest if the algorithm can be optimised.

Answer 1

Naming critique

public class GridMatch {

I'd call this something like

public class GridSearcher {

It's not the match, but the thing that looks for the match. It searches the grid for the match.

To field or not to field

    static int pInd = 0;           // current index on pattern, ie pattern.charAt(pInd) is to be searched next.

This doesn't need to be a field, since you pass it as a parameter.

    static HashMap<String, Integer> hm=null;

You don't actually use this for anything you can't get otherwise, so you can delete it and all lines referring to it. Yes, that includes the entire createMap method. Replace

        if(hm.size()==0) // every character matched for this recursion stack
            return true; 

with

        if (pInd >= pat.length()) {
            return true;
        }

And you have no need for hm.

    static int delta_i[]={ -1, -1, -1, 0, 0, 1, 1, 1 };
    static int delta_j[]={ -1, 0, 1, -1, 1, -1, 0, 1 };

These are helpful. You might as well make them final though.

    private static final int delta_i[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
    private static final int delta_j[] = { -1, 0, 1, -1, 1, -1, 0, 1 };

There doesn't seem to be any reason to use them outside the class, so mark them as private.

Just return the conditional expression

         if (row >= grid.length || row < 0 || col >= grid[0].length || col < 0)
             return false;
         else return true;

You never need to if/else return true/false. Just

         return !(row >= grid.length || row < 0 || col >= grid[row].length || col < 0);

or

         return row < grid.length && row >= 0 && col < grid[row].length && col >= 0;

Alternate version

public class GridSearcher {

    private static final int delta_i[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
    private static final int delta_j[] = { -1, 0, 1, -1, 1, -1, 0, 1 };

    private char[][] grid;

    public GridSearcher(char[][] grid) {
        this.grid = grid;
    }

    public boolean isAllowed(int row, int col){
         return (row >= 0 && row < grid.length && col >= 0 && col < grid[row].length);
    }

    public boolean searchGrid(int row, int col, String pat, boolean[][] visited, int pInd) {

        visited[row][col] = true;
        pInd++;
        if (pInd >= pat.length()) {
            return true;
        }

        for (int dir = 0; dir < delta_i.length; dir++) {
            int row_i = row + delta_i[dir];
            int col_j = col + delta_j[dir];
            if (!isAllowed(row_i, col_j) || visited[row_i][col_j]) {
                continue;
            }

            if (grid[row_i][col_j] == pat.charAt(pInd)) { 
                if (searchGrid(row_i, col_j, pat, visited, pInd)) {
                    return true;
                }
            }
        }

        // backtracking visited
        visited[row][col] = false;

        return false;
    }

    public boolean find(String needle) {
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        for (int i=0; i < grid.length; i++){
            for (int j=0; j < grid[0].length; j++) {
                if (grid[i][j] == needle.charAt(0) && searchGrid(i, j, needle, visited, 0)) {
                    return true;
                }
            }
        }

        return false;
    }

    public int getCount() {
        return grid.length * grid[0].length;
    }

    public static void main(String[] args) {
        char[][] grid
            = { { 'A', 'C', 'P', 'R', 'C' }, 
                { 'X', 'S', 'O', 'P', 'C' },
                { 'V', 'O', 'V', 'N', 'I' },
                { 'W', 'G', 'F', 'M', 'N' },
                { 'Q', 'A', 'T', 'I', 'T' } };
        GridSearcher searcher = new GridSearcher(grid);

        String [] needles = {"MICROSOFT", "ZZZ", "Oa"};
        for (String needle : needles) {
            if (searcher.find(needle)) {
                System.out.println("Present");
            } else {
                System.out.println("Not Present   " + searcher.getCount());
            }
        }

    }

}

This makes the text grid into an object field that is set in the constructor.

This moves the setup for the recursive call into its own method. So the caller only has to specify the grid and the string for which to search.

I removed a lot of code that wasn't doing anything.