https://leetcode.com/problems/stickers-to-spell-word/
People tend to come up with a greedy algorithm at a first glance: first pick the sticker that has the most letters in common with the target.
Let us show this greedy algorithm does not work.
Consider we have stickers = ["abcd", "abe", "cdf"]
and target = "abcdef"
.
By greedy, we will pick "abcd"
first because it has the most letters that is also in the target.
Then you will pick both "abe"
and "cdf"
to spell out the target.
However, as the optimal solution, picking "abe"
and "cdf"
is already enough.