FunctionRacerProblemsRace

Where the Trace Can Start

MediumRecursionPython, JavaScript, TypeScript, Java, C++

grid is a list of equal-length strings of lowercase letters. A trace of word starts in a cell holding its first letter, moves to a side neighbour (up, down, left or right) holding its second letter, and so on, one cell per letter, never using the same cell twice within one trace. Return the number of cells from which at least one complete trace of word can start. A cell counts once no matter how many traces start there.

Backtracking is the natural tool: from a cell, try each neighbour that holds the next letter, marking cells as used on the way in and freeing them on the way out.

For example, in ["abc", "bba", "cab"] the word "aba" can start from the a at the end of the middle row and from the a in the bottom row, but not from the top-left a: both b cells beside it touch no other a. The answer is 2.

Example 1

grid ["abc","bba","cab"]
word "aba"
returns 2

From the top-left a each neighbouring b touches only c and b cells, so no second a follows; the other two a cells each reach a b that touches another a.

Example 2

grid ["abc","bba","cab"]
word "ab"
returns 3

Every a cell has a b beside it, so all three a cells can start a trace of ab.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Recursion problems