691. Stickers to Spell Words
Tags:
Hard
Skills:
BFS
June 24, 2025
04:33 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu tìm số lượng sticker tối thiểu để ghép thành từ target, mỗi sticker có thể dùng nhiều lần, mỗi lần chỉ lấy từng ký tự. Đây là một bài toán thuộc dạng tối ưu hóa tổ hợp, có thể giải bằng BFS (duyệt theo trạng thái) hoặc DFS + memoization.
Approach
Time and space complexity
Solution
1function minStickers(stickers: string[], target: string): number {
2 const n = target.length;
3 const queue: number[] = [0];
4 const vis: boolean[] = Array(1 << n).fill(false);
5 for (let ans = 0; queue.length; ans++) {
6 const next_queue: number[] = [];
7 for (const cur of queue) {
8 if (cur === (1 << n) - 1) return ans;
9 for (const s of stickers) {
10 const cnt: number[] = Array(26).fill(0);
11 for (const c of s) cnt[c.charCodeAt(0) - 97]++;
12 let nxt = cur;
13 for (let i = 0; i < n; i++) {
14 const j = target.charCodeAt(i) - 97;
15 if (((cur >> i) & 1) === 0 && cnt[j]) {
16 nxt |= 1 << i;
17 cnt[j]--
18 }
19 }
20
21 if (!vis[nxt]) {
22 vis[nxt] = true;
23 next_queue.push(nxt)
24 }
25 }
26 }
27 queue.splice(0, queue.length, ...next_queue)
28 }
29 return -1
30};