FastPrepWord Path Moving Only Right or Down

Word Path Moving Only Right or Down

Compass International Holdings logoCompass International Holdings● 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 an 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 represent the grid by equal-length lowercase row strings. Both grid and word are nonempty.

For this exercise, assume the lexicographically smallest complete coordinate path must be returned. Compare at the first differing coordinate, row before column. Choose 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 = ["ccxtib","ccatni","acnntt","tcsipt","aoooaa","oaaaoo","kaicki"]word = "cat"return = [[1,0],[2,0],[3,0]]

The source1854853 grid is retained; this target and lexicographic expected path are authored.

Example 2

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

This authored example follows right then down.

Example 3

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

This authored example returns the declared empty result for absence.

Constraints

  • For this exercise, assume height and width are each from 1 through 12, and all row lengths are equal.
  • 1 <= word.length <= height + width - 1.
  • All characters are lowercase English letters.

More Compass International Holdings problems

See Compass International Holdings hiring insights
public int[][] gridPath(String[] grid, String word) {
    // Write your code here.
    return new int[0][0];
}
grid["ccxtib","ccatni","acnntt","tcsipt","aoooaa","oaaaoo","kaicki"]
word"cat"
expected[[1,0],[2,0],[3,0]]
Checking account…