commit fc94f09b9c8d3cd65899459e9b2e2e58ab3b3919
parent feda53f64a3c1e765a8886a0ac3ef5ad9722b9b5
Author: Jack Sangdahl <jack@pngu.org>
Date: Sat, 1 Nov 2025 21:50:34 -0600
691. stickers to spell word
Diffstat:
2 files changed, 109 insertions(+), 0 deletions(-)
diff --git a/stickers_spell_word.c b/stickers_spell_word.c
@@ -0,0 +1,54 @@
+// 691. Stickers to Spell Word
+#include "leetcode.h"
+
+/*
+ * we are given 'n' different types of 'stickers'. each sticker has a lowercase
+ * english word on it. you would like to spell out the given 'target' by cutting
+ * individual letters from your collection of stickers and rearranging them. you
+ * can use each sticker more than once if you want, and you have infinite
+ * quantities of each sticker. return the minimum number of stickers that you
+ * need to spell out 'target'. if the task is impossible, return -1. note in all
+ * test cases, all words were chose random from the 1000 most common us english
+ * words, and 'target' was chosen as a concatenation of two random words
+ */
+
+int find_next_state(int state, char *s, char *target, int n) {
+ for (int i = 0; s[i] != '\0'; i++) {
+ char curr = s[i];
+ for (int j = 0; j < n; j++)
+ if (!((state >> j) & 1) && target[j] == curr) {
+ state |= (1 << j);
+ break;
+ }
+ }
+ return state;
+}
+
+int minStickers(char **stickers, int stickersSize, char *target) {
+ int n = strlen(target), m = 1 << n;
+ int *dp = (int *)malloc(m * sizeof(int));
+ for (int i = 0; i < m; i++)
+ dp[i] = INT_MAX;
+ dp[0] = 0;
+ for (int state = 0; state < m; state++) {
+ if (dp[state] == INT_MAX)
+ continue;
+ for (int i = 0; i < stickersSize; i++) {
+ int new = find_next_state(state, stickers[i], target, n);
+ if (dp[state] + 1 < dp[new])
+ dp[new] = dp[state] + 1;
+ }
+ }
+ int ans = dp[m - 1];
+ if (ans == INT_MAX)
+ ans = -1;
+ free(dp);
+ return ans;
+}
+
+int main() {
+ char *s1[] = {"with", "example", "science"}, *t1 = "thehat";
+ char *s2[] = {"notice", "possible"}, *t2 = "basicbasic";
+ printf("%d\n", minStickers((char **)s1, ARRAY_SIZE(s1), t1)); // expect: 3
+ printf("%d\n", minStickers((char **)s2, ARRAY_SIZE(s2), t2)); // expect: -1
+}
diff --git a/stickers_spell_word.py b/stickers_spell_word.py
@@ -0,0 +1,55 @@
+# 691. Stickers to Spell Word
+from collections import Counter
+
+"""
+we are given 'n' different types of 'stickers'. each sticker has a lowercase
+english word on it. you would like to spell out the given 'target' by cutting
+individual letters from your collection of stickers and rearranging them. you
+can use each sticker more than once if you want, and you have infinite
+quantities of each sticker. return the minimum number of stickers that you
+need to spell out 'target'. if the task is impossible, return -1. note in all
+test cases, all words were chose random from the 1000 most common us english
+words, and 'target' was chosen as a concatenation of two random words
+"""
+
+
+class Solution(object):
+ def minStickers(self, stickers, target):
+ """
+ :type stickers: List[str]
+ :type target: str
+ :rtype: int
+ """
+ cnt = Counter(target)
+ dp = [Counter(i) & cnt for i in stickers]
+ for i in range(len(dp) - 1, -1, -1):
+ if any(dp[i] == dp[i] & dp[j] for j in range(len(dp)) if i != j):
+ dp.pop(i)
+ stickers = ["".join(i.elements()) for i in dp]
+
+ def dp(i, t):
+ if t == (1 << len(target)) - 1:
+ return 0
+ if i == len(stickers):
+ return float("inf")
+ res = dp(i + 1, t)
+ tmp = t
+ for l in stickers[i]:
+ for j, k in enumerate(target):
+ if tmp & (1 << j):
+ continue
+ if k == l:
+ tmp |= 1 << j
+ break
+ if tmp != t:
+ res = min(res, 1 + dp(i, tmp))
+ return res
+
+ ans = dp(0, 0)
+ return ans if ans != float("inf") else -1
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.minStickers(stickers=["with", "example", "science"], target="thehat"))
+ print(obj.minStickers(stickers=["notice", "possible"], target="basicbasic"))
