FastPrepMaximum Words in Disjoint Grid Paths

Maximum Words in Disjoint Grid Paths

Indeed logoIndeed● HardFULLTIMEPHONE SCREEN
Learn

Problem statement

Given a rectangular character grid and an array words, assign paths to as many word entries as possible.

Each path may start at any cell and spells its word by moving to an immediately adjacent cell to the right or directly below. Every cell may belong to at most one selected path across the entire assignment.

For this exercise, assume you return the maximum number of selected word entries, rather than paths or indices. Each array index is a separate request and can be selected at most once. Repeated spellings count separately only when assigned disjoint paths.

For this exercise, assume a nonempty rectangular board represented by equal-width lowercase row strings. Words are nonempty lowercase strings; an entry need not be present. An empty word list returns 0. Do not modify the inputs.

Function

maxDisjointWords(grid: String[], words: String[]) → int

Examples

Example 1

grid = ["aa","ba"]words = ["aa","ab"]return = 2

Authored example: put aa at [0,1],[1,1] and ab at [0,0],[1,0]. A first-path greedy choice for aa would block ab.

Example 2

grid = ["aa"]words = ["a","a","a"]return = 2

Authored example: identical entries are separate requests. Two different cells satisfy two entries; the third cannot share a cell.

Example 3

grid = ["ab","cd"]words = ["abd","ac","zz"]return = 1

Authored example: abd and ac both need [0,0], and zz is absent. Exactly one entry can be selected.

Constraints

  • For this exercise, assume grid height and width are each from 1 through 3; there are at most 9 cells.
  • For this exercise, assume 0 <= words.length <= 6, and each word has length from 1 through height + width - 1.
  • Every grid and word character is a lowercase English letter.

More Indeed problems

See Indeed hiring insights
public int maxDisjointWords(String[] grid, String[] words) {
    // Write your code here.
    return 0;
}
grid["aa","ba"]
words["aa","ab"]
expected2
Checking account…