LeetCode691. Stickers to Spell Word - f91og - 博客园

LeetCode691. Stickers to Spell Word - f91og - 博客园

We are given N different types of stickers. Each sticker has a lowercase English word on it.

You would like to spell out the given target string by cutting individual letters from your collection of stickers and rearranging them.

You can use each sticker more than once if you want, and you have infinite quantities of each sticker.

What is the minimum number of stickers that you need to spell out the target? If the task is impossible, return -1.

Example 1:

Input:

["with", "example", "science"], "thehat"

Output:

3

Explanation:

We can use 2 "with" stickers, and 1 "example" sticker. After cutting and rearrange the letters of those stickers, we can form the target "thehat". Also, this is the minimum number of stickers necessary to form the target string.

Example 2:

Input:

["notice", "possible"], "basicbasic"

Output:

-1

Explanation:

We can't form the target "basicbasic" from cutting letters from the given stickers.

分析

乍一看应该是个dp问题，但是不知道怎么建模，还是多做题目来积累经验吧。

首先是要明白题目的意思，从绕来绕去的描述中寻找题目真正要求的是什么。这题的输入是一组字符串，和一个目标字符串，对于给定的字符串可以取它任意的分割部分，同一个字符串可以使用多次，以此来组成目标字符串，求从输入的那组字符串中取最少的字符串个树来组成目标字符串。很繁琐的描述，剥离下无用信息其实就是从给定一个字符串集合S,以及一个目标字符串T.求使用S中字符串的最小个数，能够满足T需要的字符数。

利用数组下标与值的映射关系来存储每个sticker以及target string中的字符及其数目，并且使用回溯来遍历所有的可能。

看了下递归遍历的代码，还是不是很懂，还是去看了下dp的解法。利用dp加上回溯递归的方法遍历求解所有的可能。对于每一个sticker，应用到组成target string的话，组成了一部分，还剩下了一部分，这样递归求解即可。

利用一个map存储dp数组，key是要组成的target string，值是最优解，也就最少使用多少个sticker。

dp[s] is the minimum stickers required for string s (-1 if impossible). Note s is sorted. clearly, dp[""] = 0, and the problem asks for dp[target].

状态转移方程：

dp[s] = min(1+dp[reduced_s]) for all stickers,  here reduced_s is a new string after certain sticker applied

Read full article from LeetCode691. Stickers to Spell Word - f91og - 博客园