Problem Brief

Can Fit the Word

PHONE SCREEN

See Google online assessment and hiring insights

Hi! The outputs are just placeholders. This problem is here to give you a glimpse of what a Google interviewer asked in one of their phone screens today. And today is 03-27-2025

We are given a grid of size N*M having characters "#", "" (empty space), and any English lowercase alphabet letter.

"#": Filled
"": Empty
Any English alphabet letter

We are also given a string word. We have to find if we can fit this word in the grid either by directly matching with English alphabet letters or using the empty spaces (by filling them with matching characters). The word should match exactly, and no empty space should be left before and after. We can have the word match from left to right and top to bottom only.

1Example 1

Input

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

Output

Explanation

The word ALA does not fit as we have one space left at the end.

      #### ####
      L_# ALA_# 
      #X#__ #X#__

2Example 2

Input

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

Output

Explanation

The word ALAN fits.

      #### ####
      L_# ALAN# 
      #X#__ #X#__