← Questions

Spell a word with letter blocks, one block per letter

0
AmazonCoding

You have a set of letter blocks. Each block is a list of lowercase characters printed on its faces. You also get a target string.

Implement can_form(blocks: list[list[str]], target: str) -> bool. Return True if you can spell target by taking one character from a block for each position of target, where:

  • each block is used for at most one position,
  • the blocks can be used in any order, and
  • a block that shows the same letter twice still counts as one block.

Constraints: 0 <= len(target) <= 1000, 0 <= len(blocks) <= 1000, each block has 1 to 26 characters.

Example 1

blocks = [["m", "q"], ["o", "p"], ["p", "m"]]
target = "mop"
-> True   # m from block 0, o from block 1, p from block 2

Example 2

blocks = [["r", "s"], ["r"], ["t"]]
target = "rrs"
-> False  # only two blocks have 'r', and one of them is also the only block with 's'

A natural follow-up: return which block is used for each position of target.

Reconstructed from the reported question; details may differ from what interviewers ask.

Write and test your solution herePython in your browser, the question's tests level by level, every submission kept for you.Sign in to start coding