691.贴纸拼词.md

691.贴纸拼词

/*
 * @lc app=leetcode.cn id=691 lang=typescript
 *
 * [691] 贴纸拼词
 */

// @lc code=start
function minStickers(stickers: string[], target: string): number {}
// @lc code=end

解法 1: 记忆化搜索

function minStickers(stickers: string[], target: string): number {
  if (stickers.filter(word => word === target).length) return 1

  const map = new Map<string, Map<string, number>>()
  for (let word of [...stickers, target]) {
    const count = new Map<string, number>()
    for (let char of word) {
      count.set(char, (count.get(char) ?? 0) + 1)
    }
    map.set(word, count)
  }
  const cache = new Map<string, number>()
  const dfs = (i: number, rem: Map<string, number>) => {
    if (i >= stickers.length) return Infinity
    const state =
      i +
      [...rem.entries()]
        .sort((a, b) => (a[0] < b[0] ? -1 : 1))
        .map(arr => arr.join(','))
        .join(',')
    if (cache.has(state)) return cache.get(state)!

    const cur = map.get(stickers[i])!
    let max = 0,
      common: string[] = [],
      tmp = new Map<string, number>()
    for (let [char, num] of rem) {
      tmp.set(char, num)
      if (cur.has(char)) {
        max = Math.max(max, Math.ceil(num / cur.get(char)!))
        common.push(char)
      }
    }

    let res = Infinity
    for (let j = 0; j <= max; j++) {
      for (let char of common) {
        tmp.set(char, tmp.get(char)! - j * cur.get(char)!)
        if (tmp.get(char)! <= 0) tmp.delete(char)
      }
      if (tmp.size === 0) {
        res = Math.min(res, j)
      } else {
        res = Math.min(res, j + dfs(i + 1, tmp))
      }
      for (let char of common) {
        tmp.set(char, rem.get(char)!)
      }
    }
    cache.set(state, res)
    return res
  }
  let res = dfs(0, map.get(target)!)

  return res === Infinity ? -1 : res
}

Case

test.each([
  {
    input: {
      stickers: ['claim', 'last', 'determine', 'cry', 'bed', 'result', 'human', 'duck', 'seem'],
      target: 'camereal',
    },
    output: 3,
  },
  { input: { stickers: ['with', 'example', 'science'], target: 'thehat' }, output: 3 },
  { input: { stickers: ['notice', 'possible'], target: 'basicbasic' }, output: -1 },
])('input: stickers = $input.stickers, target = $input.target', ({ input: { stickers, target }, output }) => {
  expect(minStickers(stickers, target)).toEqual(output)
})