Spell a word with letter blocks, one block per letter
I was asked this
No reports yet. Sign in to say where you were asked it.
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.
Sign in to see the worked answer
The full answer, chapter by chapter, with what interviewers expect at each level. Free with an account: one full answer per company.
Sign in to see the worked answer
The full answer, chapter by chapter, with what interviewers expect at each level. Free with an account: one full answer per company.
Sign in to submit your code; every attempt is kept here.
