困难题:深度优先搜索+记忆体+二进制
解:
target最长也就15,每一次拿sticker都最少满足小区target中一个字母,所以可以用深度优先搜索,最深也就15层;
当前状态是剩余未满足的target单词,每次有len(stickers)种选择;
会有重复,采用记忆体。
状态如何表示?使用二进制编码:0为未满足,1为满足
二进制操作:
生成长度为m的连续1:
(1<<m)-1
一个二进制数
x
, 对从左数第 n位取反:x^=1<<(n-1)
查看第i位是否为1:
x>>i&1
(相当于.....x & 0000001进行&,前面都是0,最后一位为1,则为1,否则为0)
总结:
- 多叉树结构
- 记忆体
- 二进制===>hashable,高效