FastPrepWord Path Moving Only Up or Right

Word Path Moving Only Up or Right

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 directly above or to the right.

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 up before right 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

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

Examples

Example 1

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

This authored example moves up from [1,0] to [0,0]; moving down cannot spell this word.

Example 2

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

This authored example moves up and then right.

Example 3

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

This authored example has no valid up/right path.

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[][] upRightPath(String[] grid, String word) {
    // Write your code here.
    return new int[0][0];
}
grid["bd","ac"]
word"ab"
expected[[1,0],[0,0]]
Checking account…