Count of number of given string in 2D character array

The problem, simply

You get a grid of letters with R rows and C columns, and a word of length L. Count how many different paths spell the word.

A path starts on any box and steps to a box that touches it on a side: up, down, left or right. It may turn at every step, like a snake. It may not use the same box twice. Two paths are different if they use different boxes.

This is the bending version. The sister problem "Search a word in a 2D grid" only reads in straight lines.

A story to remember it

Picture it

Examples

Way 1: the simple way

Walk every snake path of length L from every box, without looking at the letters on the way. Only when a path is L boxes long, read its letters and compare them with the word.

1. From each box, walk every path of L boxes that never reuses a box.
2. At full length, spell the path and compare it with the word.
3. Count the matches.

class Solution {
    public int countWord(char[][] grid, String word) {
        int R = grid.length, C = grid[0].length, total = 0;
        boolean[][] used = new boolean[R][C];
        for (int r = 0; r < R; r++)
            for (int c = 0; c < C; c++)
                total += walk(grid, used, r, c, new StringBuilder(), word);
        return total;
    }

    private int walk(char[][] g, boolean[][] used, int r, int c, StringBuilder path, String word) {
        if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || used[r][c]) return 0;
        path.append(g[r][c]);
        used[r][c] = true;
        int found;
        if (path.length() == word.length()) {
            found = path.toString().equals(word) ? 1 : 0;   // check only at the very end
        } else {
            found = walk(g, used, r, c + 1, path, word) + walk(g, used, r + 1, c, path, word)
                  + walk(g, used, r, c - 1, path, word) + walk(g, used, r - 1, c, path, word);
        }
        used[r][c] = false;                                 // step back
        path.deleteCharAt(path.length() - 1);
        return found;
    }
}

How long it takes: from each of the R * C boxes there are up to 4 * 3^(L-2) paths, because after the first hop you can never go straight back. Each full path is compared in O(L). So O(R * C * 3^L * L). Extra room: the path and the call stack, O(L).

Way 2: the clever way

Check letters while you hop, not at the end. If the box you step on is not the next letter of the word, stop right there. That cuts off almost every path after one or two hops.

1. For each box, start a search with letter number k = 0.
2. If the box is off the grid, or its letter is not word[k], return 0. A box marked with chalk holds #, so it fails this test too.
3. If k is the last letter, return 1.
4. Otherwise mark the box with #, add up the searches in the four directions with k + 1, then put the letter back and return the sum.

class Solution {
    public int countWord(char[][] grid, String word) {
        if (word.isEmpty()) return 0;
        int total = 0;
        for (int r = 0; r < grid.length; r++)
            for (int c = 0; c < grid[0].length; c++)
                total += hop(grid, word, r, c, 0);
        return total;
    }

    private int hop(char[][] g, String word, int r, int c, int k) {
        if (r < 0 || c < 0 || r >= g.length || c >= g[0].length) return 0;
        if (g[r][c] != word.charAt(k)) return 0;      // wrong letter or chalk mark: stop now
        if (k == word.length() - 1) return 1;          // spelled the whole word

        char keep = g[r][c];
        g[r][c] = '#';                                 // chalk mark: used on this path
        int found = hop(g, word, r, c + 1, k + 1) + hop(g, word, r + 1, c, k + 1)
                  + hop(g, word, r, c - 1, k + 1) + hop(g, word, r - 1, c, k + 1);
        g[r][c] = keep;                                // rub the mark out when stepping back
        return found;
    }
}

How long it takes: in the worst case, like a grid full of A and the word AAAA, every path matches and it is still O(R * C * 3^L). On normal grids most starting boxes fail at once, so it is far faster than Way 1. Extra room: the call stack is at most L deep, O(L).

Watch out for

• Check the bounds before you read g[r][c], or the program crashes at the edges.
• Return 1 as soon as the last letter matches. If you wait one more hop and return 1 there, a finished path is counted once for every neighbor of its last box.
• Using # as the mark assumes the word has no #. A separate boolean[][] is safer when letters can be anything.
• Ask whether diagonal hops are allowed. If so, add the four diagonal directions.

What interviewers ask next

• Only say whether the word exists (LeetCode 79)? Same search, but return true the moment one path finishes.
• Find many words at once (LeetCode 212)? Put all words in a trie and walk the grid once, following the trie as you hop. Words that share a start share the work.
• Can you prune more? Count the letters in the grid first. If the word needs more of some letter than the grid has, return 0 at once. Also start from whichever end of the word has the rarer letter.
• What if the word must be in a straight line? Then no backtracking is needed. Try the 8 straight directions from each box, like a word search puzzle.

Remember this

Grown-up words: hopping and stepping back is backtracking, the hops form a depth first search, the chalk mark is the visited marker, stopping on a wrong letter is pruning, and the waiting hops are the recursion call stack.