FastPrepWord Path Moving Only Right or Down

Word Path Moving Only Right or Down

Wayfair logoWayfair● 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.

Return one coordinate [row,column] for every letter, in word order. For this exercise, assume zero-based coordinates and equal-length lowercase row strings. Do not modify the input.

For this exercise, assume the lexicographically smallest complete coordinate path must be returned: compare the first differing coordinate by row, then column. Try starting cells in row-major order and prefer right before down only when that continuation can complete the word.

For this exercise, assume the word may be absent. Return an empty coordinate array when no permitted path spells it.

Function

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

Examples

Example 1

grid = ["ab","bd"]word = "abd"return = [[0,0],[0,1],[1,1]]

Authored example: both a-right-b-down-d and a-down-b-right-d work. The right continuation gives the lexicographically smaller coordinate path.

Example 2

grid = ["ax","bc"]word = "abc"return = [[0,0],[1,0],[1,1]]

Authored example: the path moves down and then right; the right neighbor of the start cannot supply b.

Example 3

grid = ["ab","cd"]word = "acb"return = []

Authored example: a can move down to c, but no permitted next cell contains b, so no complete path exists.

Constraints

  • For this exercise, assume grid height R and width C are each from 1 through 12, with all rows equally long.
  • For this exercise, assume 1 <= word.length <= 23. A target longer than any possible right/down path is valid and returns an empty result.
  • For this exercise, assume all grid and word characters are lowercase English letters.

More Wayfair problems

See Wayfair hiring insights
public int[][] gridPath(String[] grid, String word) {
    // Write your code here.
    return new int[0][0];
}
grid["ab","bd"]
word"abd"
expected[[0,0],[0,1],[1,1]]
Checking account…