FastPrep
Problem · Matrix

Can Fit the Word

Learn this problem
● MediumGooglePHONE SCREEN
See Google hiring insights

Problem statement

You are given a rectangular character grid containing blocked cells #, empty cells _, and English letters, plus a string word.

A slot is a maximal contiguous run of non-blocked cells in one row or one column. The word fits when a slot has exactly the same length as the word and, reading left-to-right or top-to-bottom, every slot cell is either _ or already equals the corresponding word character. Empty cells may be filled with the required letters.

Return 1 if the word fits in at least one slot; otherwise return 0.

Function

canFitTheWord(grid: char[][], word: String) → int

Examples

Example 1

grid = [['#', '#', '#', '#'], ['L', '_', '#', '#'], ['A', 'L', 'A', '_'], ['#', 'X', '#', '#']]word = "ALA"return = 0

The row containing ALA_ is a four-cell slot, so placing the three-letter word would leave one empty cell. No vertical slot matches.

Example 2

grid = [['#', '#', '#', '#'], ['L', '_', '#', '#'], ['A', 'L', 'A', 'N'], ['#', 'X', '#', '#']]word = "ALAN"return = 1

The third row is one complete four-cell slot and exactly spells ALAN.

Constraints

  • grid is non-empty and rectangular.
  • Every grid cell is #, _, or an English letter.
  • word is non-empty and contains English letters.

More Google problems

drafts saved locally
public int canFitTheWord(char[][] grid, String word) {
  // write your code here
}
grid[['#', '#', '#', '#'], ['L', '_', '#', '#'], ['A', 'L', 'A', '_'], ['#', 'X', '#', '#']]
word"ALA"
expected0
checking account