广度优先搜索，深度优先搜索 + 贪心算法 + 掩码：求解《691. 贴纸拼词》
2022-05-14 18:38:15
广度优先搜索，深度优先搜索 + 贪心算法 + 掩码，求解《691. 贴纸拼词》
代码模板
多叉树层序遍历
const queue = [root]
let index = 0, distance = 0 // 移动 index 指针，代替数组的 shift() 或拷贝操作，提高性能
while (index < queue.length) {
distance++
const length = queue.length
while (index < length) {
const node = queue[index] // 拿到节点，distance 就是节点到根节点的距离
// do something （本题，我们来算空闲时间，并更新最大值）
index++
for (const child of node) queue.push(child)
}
}例题
691. 贴纸拼词
我们有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。
您想要拼写出给定的字符串 target ，方法是从收集的贴纸中切割单个字母并重新排列它们。如果你愿意，你可以多次使用每个贴纸，每个贴纸的数量是无限的。
返回你需要拼出 target 的最小贴纸数量。如果任务不可能，则返回 -1 。
注意：在所有的测试用例中，所有的单词都是从 1000 个最常见的美国英语单词中随机选择的，并且 target 被选择为两个随机单词的连接。
答案
广度优先搜索 + 层序遍历
var minStickers = function(stickers, target) {
const q = [target], visited = new Set()
let depth = -1, index = 0
while (index < q.length) {
depth++
for (const l = q.length; index < l; index++) {
const n = q[index]
if (n.length === 0) return depth
for (let i = 0; i < stickers.length; i++) {
const sticker = stickers[i]
const cnt = new Uint8Array(26)
for (let j = 0; j < sticker.length; j++) {
cnt[sticker.charCodeAt(j) - 97]++
}
let a = n.split('')
for (let j = a.length; j--;) {
if (cnt[a[j].charCodeAt() - 97] > 0) {
cnt[a[j].charCodeAt() - 97]--
a.splice(j, 1)
}
}
if (a.length === n.length) continue
const s = a.join('')
if (visited.has(s)) continue
visited.add(s)
q.push(s)
}
}
}
return -1
};深度优先搜索 + 贪心算法 + 掩码
贪心策略：每次总是取能改变最多的纸条
var minStickers = function(stickers, target) {
const n = target.length
const memo = new Uint8Array(2 ** n)
const d = mask => {
if (mask === 0) return 0
if (memo[mask] > 0) return memo[mask]
let r = n + 1
for (let i = 0; i < stickers.length; i++) {
let left = mask
const cnt = new Uint8Array(26)
for (let j = 0; j < stickers[i].length; j++) cnt[stickers[i].charCodeAt(j) - 97]++
for (let j = 0; j < n; j++) {
if ((mask & 1 << j) > 0 && cnt[target.charCodeAt(j) - 97] > 0) {
cnt[target.charCodeAt(j) - 97]--
left ^= 1 << j
}
}
if (left < mask) r = Math.min(r, d(left) + 1)
}
return memo[mask] = r
}
const r = d(2 ** n - 1)
return r > n ? -1 : r
};
function minStickers(stickers: string[], target: string): number {
const n = target.length
const memo = new Uint8Array(2 ** n)
const d = mask => {
if (mask === 0) return 0
if (memo[mask] > 0) return memo[mask]
let r = n + 1
for (let i = 0; i < stickers.length; i++) {
let left = mask
const cnt = new Uint8Array(26)
for (let j = 0; j < stickers[i].length; j++) cnt[stickers[i].charCodeAt(j) - 97]++
for (let j = 0; j < n; j++) {
if ((mask & 1 << j) > 0 && cnt[target.charCodeAt(j) - 97] > 0) {
cnt[target.charCodeAt(j) - 97]--
left ^= 1 << j
}
}
if (left < mask) r = Math.min(r, d(left) + 1)
}
return memo[mask] = r
}
const r = d(2 ** n - 1)
return r > n ? -1 : r
};func minStickers(stickers []string, target string) int {
n := len(target)
mask := int(math.Pow(2, float64(n))) - 1
memo := make([]int, mask + 1)
var d func(mask int) int
d = func(mask int) int {
if mask == 0 {
return 0
}
if memo[mask] > 0 {
return memo[mask]
}
r := n + 1
for _, sticker := range stickers {
left, cnt := mask, make([]int, 26)
for _, charCode := range sticker {
cnt[charCode - 97]++
}
for i, charCode := range target {
if (mask & (1 << i)) > 0 && cnt[charCode - 97] > 0 {
cnt[charCode - 97]--
left ^= 1 << i
}
}
if left < mask {
r = min(r, d(left) + 1)
}
}
memo[mask] = r
return r
}
r := d(mask)
if r > n {
return -1
} else {
return r
}
}
func min(a int, b int) int {
if a < b {
return a
}
return b
}class Solution {
private $memo = array();
function minStickers($stickers, $target) {
$n = strlen($target);
$this->memo = array_fill(0, 2 ** $n, 0);
$r = $this->d(2 ** $n - 1, $stickers, $target);
return $r > $n ? -1 : $r;
}
function d($mask, $stickers, $target) {
if ($mask === 0) return 0;
if ($this->memo[$mask] > 0) return $this->memo[$mask];
$n = strlen($target);
$r = $n + 1;
foreach($stickers as $sticker) {
$left = $mask;
$cnt = array_fill(0, 26, 0);
for ($i = 0; $i < strlen($sticker); $i++) {
$cnt[ord($sticker[$i]) - 97]++;
}
for ($i = 0; $i < $n; $i++) {
if (($mask & 1 << $i) > 0 && $cnt[ord($target[$i]) - 97] > 0) {
$cnt[ord($target[$i]) - 97]--;
$left ^= 1 << $i;
}
}
if ($left < $mask) {
$r = min($r, $this->d($left, $stickers, $target) + 1);
}
}
return $this->memo[$mask] = $r;
}
}
