FastPrepWord Path Moving Only Right or Down

Word Path Moving Only Right or Down

Indeed logoIndeed● MediumFULLTIMEPHONE SCREEN
Learn

Problem statement

Find a path spelling word in a rectangular character grid. The word may start at any cell. Each next letter must be in the immediately adjacent cell to the right or directly below the current cell. The word is guaranteed to be present.

Return one coordinate [row,column] for each letter, in word order. For this exercise, assume zero-based coordinates and represent the grid as an array of equal-length row strings.

The source permits any valid path. For this exercise, assume the lexicographically smallest complete coordinate path must be returned. Compare paths at the first differing coordinate, comparing row before column. This chooses starting cells in row-major order and prefers a feasible right continuation over a feasible down continuation.

For this exercise, assume all grid and word characters are lowercase English letters and both the grid and word are nonempty.

Function

gridPath(grid: String[], word: String) → int[][]

Examples

Example 1

grid = ["cctnax","ccatnt","acnntt","tniipp","aoooaa","saaaoo","kaioki"]word = "catnip"return = [[1,1],[1,2],[1,3],[2,3],[3,3],[3,4]]

The path spells catnip using only adjacent right and down moves.

Example 2

grid = ["cctnax","ccatnt","acnntt","tniipp","aoooaa","saaaoo","kaioki"]word = "cccc"return = [[0,0],[0,1],[1,1],[2,1]]

The source accepts either listed path. For this exercise the lexicographically smallest path goes right from [0,0] before going down.

Constraints

  • For this exercise, assume grid height and width are each from 1 through 30.
  • All row strings have the same length.
  • 1 <= word.length <= height + width - 1.
  • At least one right/down path spells the word.

More Indeed problems

See Indeed hiring insights
public int[][] gridPath(String[] grid, String word) {
    // Write your code here.
    return new int[0][0];
}
grid["cctnax","ccatnt","acnntt","tniipp","aoooaa","saaaoo","kaioki"]
word"catnip"
expected[[1,1],[1,2],[1,3],[2,3],[3,3],[3,4]]
Checking account…