Question

691. 贴纸拼词

English Version

题目描述

我们有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。

您想要拼写出给定的字符串 target ，方法是从收集的贴纸中切割单个字母并重新排列它们。如果你愿意，你可以多次使用每个贴纸，每个贴纸的数量是无限的。

返回你需要拼出 target 的最小贴纸数量。如果任务不可能，则返回 -1 。

注意：在所有的测试用例中，所有的单词都是从 1000 个最常见的美国英语单词中随机选择的，并且 target 被选择为两个随机单词的连接。

 

示例 1：

输入： stickers = ["with","example","science"], target = "thehat"
输出：3
解释：
我们可以使用 2 个 "with" 贴纸，和 1 个 "example" 贴纸。
把贴纸上的字母剪下来并重新排列后，就可以形成目标 “thehat“ 了。
此外，这是形成目标字符串所需的最小贴纸数量。

示例 2:

输入：stickers = ["notice","possible"], target = "basicbasic"
输出：-1
解释：我们不能通过剪切给定贴纸的字母来形成目标“basicbasic”。

 

提示:

• n == stickers.length
• 1 <= n <= 50
• 1 <= stickers[i].length <= 10
• 1 <= target.length <= 15
• stickers[i] 和 target 由小写英文单词组成

解法

方法一：BFS + 状态压缩

class Solution:
  def minStickers(self, stickers: List[str], target: str) -> int:
    q = deque([0])
    ans = 0
    n = len(target)
    vis = [False] * (1 << n)
    vis[0] = True
    while q:
      for _ in range(len(q)):
        state = q.popleft()
        if state == (1 << n) - 1:
          return ans
        for s in stickers:
          nxt = state
          cnt = Counter(s)
          for i, c in enumerate(target):
            if not (nxt & (1 << i)) and cnt[c]:
              nxt |= 1 << i
              cnt[c] -= 1
          if not vis[nxt]:
            vis[nxt] = True
            q.append(nxt)
      ans += 1
    return -1

class Solution {
  public int minStickers(String[] stickers, String target) {
    Deque<Integer> q = new ArrayDeque<>();
    q.offer(0);
    int ans = 0;
    int n = target.length();
    boolean[] vis = new boolean[1 << n];
    vis[0] = true;
    while (!q.isEmpty()) {
      for (int t = q.size(); t > 0; --t) {
        int state = q.poll();
        if (state == (1 << n) - 1) {
          return ans;
        }
        for (String s : stickers) {
          int nxt = state;
          int[] cnt = new int[26];
          for (char c : s.toCharArray()) {
            ++cnt[c - 'a'];
          }
          for (int i = 0; i < n; ++i) {
            int idx = target.charAt(i) - 'a';
            if ((nxt & (1 << i)) == 0 && cnt[idx] > 0) {
              nxt |= 1 << i;
              --cnt[idx];
            }
          }
          if (!vis[nxt]) {
            vis[nxt] = true;
            q.offer(nxt);
          }
        }
      }
      ++ans;
    }
    return -1;
  }
}

class Solution {
public:
  int minStickers(vector<string>& stickers, string target) {
    queue<int> q{{0}};
    int ans = 0;
    int n = target.size();
    vector<bool> vis(1 << n);
    vis[0] = true;
    while (!q.empty()) {
      for (int t = q.size(); t; --t) {
        int state = q.front();
        if (state == (1 << n) - 1) return ans;
        q.pop();
        for (auto& s : stickers) {
          int nxt = state;
          vector<int> cnt(26);
          for (char& c : s) ++cnt[c - 'a'];
          for (int i = 0; i < n; ++i) {
            int idx = target[i] - 'a';
            if (!(nxt & (1 << i)) && cnt[idx]) {
              nxt |= 1 << i;
              --cnt[idx];
            }
          }
          if (!vis[nxt]) {
            vis[nxt] = true;
            q.push(nxt);
          }
        }
      }
      ++ans;
    }
    return -1;
  }
};

func minStickers(stickers []string, target string) int {
  q := []int{0}
  n := len(target)
  vis := make([]bool, 1<<n)
  vis[0] = true
  ans := 0
  for len(q) > 0 {
    for t := len(q); t > 0; t-- {
      state := q[0]
      if state == (1<<n)-1 {
        return ans
      }
      q = q[1:]
      for _, s := range stickers {
        nxt := state
        cnt := make([]int, 26)
        for _, c := range s {
          cnt[c-'a']++
        }
        for i, c := range target {
          idx := c - 'a'
          if (nxt&(1<<i)) == 0 && cnt[idx] > 0 {
            nxt |= 1 << i
            cnt[idx]--
          }
        }
        if !vis[nxt] {
          vis[nxt] = true
          q = append(q, nxt)
        }
      }
    }
    ans++
  }
  return -1
}

use std::collections::{ HashSet, VecDeque };

impl Solution {
  pub fn min_stickers(stickers: Vec<String>, target: String) -> i32 {
    let mut q = VecDeque::new();
    q.push_back(0);
    let mut ans = 0;
    let n = target.len();
    let mut vis = HashSet::new();
    vis.insert(0);
    while !q.is_empty() {
      for _ in 0..q.len() {
        let state = q.pop_front().unwrap();
        if state == (1 << n) - 1 {
          return ans;
        }
        for s in &stickers {
          let mut nxt = state;
          let mut cnt = [0; 26];
          for &c in s.as_bytes() {
            cnt[(c - b'a') as usize] += 1;
          }
          for (i, &c) in target.as_bytes().iter().enumerate() {
            let idx = (c - b'a') as usize;
            if (nxt & (1 << i)) == 0 && cnt[idx] > 0 {
              nxt |= 1 << i;
              cnt[idx] -= 1;
            }
          }
          if !vis.contains(&nxt) {
            q.push_back(nxt);
            vis.insert(nxt);
          }
        }
      }
      ans += 1;
    }
    -1
  }
}