634. Sticker Spelling

Hard7.5 points estimatedStringBacktrackingDynamic ProgrammingBitmaskMemoisation3 hints
RPby Rohit Parihar

A craft shop sells letter stickers. Every element of stickers is a sheet of lowercase letters, and the shop has an unlimited supply of each sheet. You may cut single letters out of a sheet, and a sheet you buy can be cut for as many of its letters as you wish; unused letters are thrown away.

Return the smallest number of sheets needed to cut out all the letters of target (in any order, each letter of the target needing its own cut-out letter). If the target cannot be built with the given sheets, return -1.

Example 1

Input:
stickers = ["abc","bde","cdd"], target = "badcd"
Output:
2
Explanation:

Cut b, a and c from abc and both d letters from cdd: two sheets. One sheet cannot hold all the letters.

Example 2

Input:
stickers = ["xy","yz"], target = "xyzzy"
Output:
3
Explanation:

xy gives x and y; yz gives y and z; one more yz gives the second z. Three sheets, and the letters spell xyzzy with one y left over.

Example 3

Input:
stickers = ["abc","def"], target = "cafe"
Output:
2
Explanation:

No sheet contains an e together with the others, but abc gives c and a, and def gives f and e, so two sheets suffice.

Constraints

  • 1 ≤ stickers.length ≤ 8
  • 1 ≤ stickers[i].length ≤ 8
  • 1 ≤ target.length ≤ 12
  • All strings consist of lowercase English letters.

How this problem is judged

Answers
Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Time per case
Python 400 msC++ 100 msJava 200 msJavaScript 200 msTypeScript 200 ms

Expected complexity

Time
O(2^T * S * (T + L))
Space
O(2^T)

What the author was aiming for. Your own solution is not measured against it.

Asked in an interview

Were you asked this in an interview? Say where, anonymously.

Code
Loading the editor…