Find word in a grid of characters

Question

I have to find how many times a given string can be built from a 2D grid of letters:

To build the word, I can start anywhere then move from cell to cell in one of 3 directions:

a) same row, next column (right)
b) next row, same column (down)
c) next row, next column (diagonal right and down)

Example:

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

String str = "aa";

output:
5

Explanation:
a) [0,0][0,1]
b) [0,0][1,0]
c) [1,0][1,1]
d) [0,1][1,1]
e) [0,0][1,1]

This is my code so far:

class Solution {
    
    public boolean exist(char[][] grid, String str) {
        int m=grid.length,n=grid[0].length;
        boolean[][] visited=new boolean[m][n];
        int result = 0;
        for (int i=0;i< m;i++){
            for (int j=0;j<n;j++){               
                if (dfs(grid,visited,i,j,0,str)){
                    result++;
                }              
            }
        }
        return result;
    }
    private boolean dfs(char[][] grid, boolean[][] visited, int x, int y, int i, String str){         
        int m=grid.length,n=grid[0].length;   
        if (i==str.length()) return true;
        
        if(x<0||x>=m||y<0||y>=n) return false;
        if(visited[x][y]) return false;
        if(grid[x][y]!=str.charAt(i)) return false;
        int[][] dirs={{1,0},{0,1},{1,1}};
        visited[x][y]=true;
        for (int[] dir: dirs){
            int x1=x+dir[0], y1=y+dir[1];
            if (dfs(grid, visited, x1, y1, i+1, str)){
                return true;
            }
        }
        visited[x][y]=false;
        return false;                                                                          
    }
}

For the sample input I mentioned above I am able to get result as 2 instead of 5.

How can I fix this?
Is there any other better approach?

Answer 1

Start at 0,0 work across the columns and down the rows. Create a method boolean check(String word, int startRow, int startCol, int dRow, int dCol) it will return true if the word is found beginning at startRow,startCol incrementing the column by dCol and the row by dRow after finding each letter. It can return false immediately if the letter being checked doesn't match or if the row or column would be out of bounds. Call it three times in the loop, first with dRow = 0 and dCol = 1, then with both set to 1, then with dRow = 1 and dCol = 0.

Name your methods better dfs is not a good name.

Here's my version, not exactly as described above. I've decided to return an int rather than a boolean so I can easily add the result to the total. I've hard-coded a grid of letters just to simplify the example.

public class FindWord {
    static char [][] grid = {
        {'b','a','d'},
        {'o','a','k'},
        {'d','a','d'}
    };
    static final int cols = grid[0].length;
    static final int rows = grid.length;

    public static void main(String[] args) {
        countWords("bad");
        countWords("dad");
        countWords("oak");
        countWords("bod");
        countWords("bid");
        countWords("aaa");
        countWords("aa");
        countWords("d");
    }

    private static void countWords(String word) {
        int total = 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                total += find(word,r,c,0,1) // across
                    + find(word,r,c,1,1) // diagonal
                    + find(word,r,c,1,0); // down
            }
        }
        System.out.println(total);
    }

    private static int find(String word, int row, int col, int dRow, int dCol) {
        for (char letter :  word.toCharArray()) {
            if (row >= rows || col >= cols || grid[row][col] != letter)
                return 0;
            row += dRow;
            col += dCol;
        }
        return 1;
    }
}

You might notice that this example has a bug for one letter words. It counts one letter words 3 times because it considers the same starting position as across, diagonal, and down. That is easy to fix with a condition to only check the "across" case and not the other two if the word length is one. I'll leave it to you to make that adjustment.