Ward Swab Reading Route

Lexicographically smallest grid path spelling a string with exactly k turns

MediumBacktrackingGrid SearchLexicographic Ordering

A hospital ward stores labeled swab stations in a rectangular grid. Each station has one uppercase letter, given by the corresponding character in grid.

A technician must visit stations whose letters spell prescription, in order. The technician may start at any station, and each move must go to an orthogonally adjacent station: up, down, left, or right. A station may not be visited more than once.

The route must make exactly turns direction changes. A direction change occurs when a move has a different direction from the preceding move. The first move does not count as a direction change, and a route containing only one station has zero direction changes.

Number the stations in row-major order, starting at zero. For a grid with C columns, station (r, c) has index r * C + c.

Return the lexicographically smallest list of station indices among all valid routes. Lists are compared at their first differing index, with the smaller index coming first. Return an empty list if no valid route exists.

Examples

Example 1

Input: grid = ["ABX","DCX"], prescription = "ABCD", turns = 2
Output: [0,1,4,3]

One route spells ABCD by visiting stations 0, 1, 4, and 3. Its moves are right, down, and left, so it makes two direction changes. It is the lexicographically smallest valid route.

Example 2

Input: grid = ["AAA","AAA"], prescription = "AAA", turns = 0
Output: [0,1,2]

Every station has the required label. Starting at station 0, the smallest possible next station is 1. Continuing to station 2 gives a straight route with no direction changes, so the selected route visits 0, 1, and 2.

Example 3

Input: grid = ["ABC"], prescription = "ABC", turns = 1
Output: []

The letters A, B, and C can be read along the row, but that route has no direction changes. No route meets the requested turn count.

Constraints

  • 1 <= len(grid) <= 4
  • 1 <= len(grid[0]) <= 4
  • All rows of grid have the same length.
  • Every grid character and prescription character is an uppercase English letter.
  • 1 <= len(prescription) <= min(12, len(grid) * len(grid[0]))
  • 0 <= turns <= max(0, len(prescription) - 2)

The output is always uniquely determined by the lexicographic rule. The intended solution uses backtracking, turn-count bounds, and memoization of failed search states. With N stations and prescription length L, a coarse search-tree bound is O(N * 3^(L-1)); the visited-station restriction and memoization reduce repeated work.

Hints

Show hint 1

Try starting stations and neighboring stations in increasing index order. How does this affect the first complete route you find?

Show hint 2

Track the visited stations, previous move direction, and turns used. Prune a branch if it has already used too many turns or cannot reach the requested total with its remaining moves.

Follow-up questions

What an interviewer might ask once you have a working solution.

  • How would you change the search to count valid routes rather than return one route?
  • How would you support stations that may each be visited up to a specified number of times?

Practice this with an AI interviewer

Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.

Start this problem