Skip to content

困难题:深度优先搜索+记忆体+二进制

691. 贴纸拼词

解:

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)

总结:

  1. 多叉树结构
  2. 记忆体
  3. 二进制===>hashable,高效