add stickers-to-spell-word.cpp

kamyu104 · kamyu104 · commit 5132fe7041f8 · 2017-10-09T21:02:09.000+08:00
diff --git a/C++/stickers-to-spell-word.cpp b/C++/stickers-to-spell-word.cpp
@@ -0,0 +1,49 @@
+// Time:  O(T * S^T)
+// Space: O(T * S^T)
+
+class Solution {
+public:
+    int minStickers(vector<string>& stickers, string target) {
+        vector<vector<int>> sticker_counts(stickers.size(), vector<int>(26));
+        unordered_map<string, int> dp;
+        for (int i = 0; i < stickers.size(); ++i) {
+            for (const auto& c : stickers[i]) {
+                ++sticker_counts[i][c - 'a'];
+            }
+        }
+        dp[""] = 0;
+        return minStickersHelper(sticker_counts, target, &dp);
+    }
+    
+private:
+    int minStickersHelper(const vector<vector<int>>& sticker_counts, const string& target,
+                          unordered_map<string, int> *dp) {
+        if (dp->count(target)) {
+            return (*dp)[target];
+        }
+        int result = numeric_limits<int>::max();
+        vector<int> target_count(26);
+        for (const auto& c : target) {
+            ++target_count[c - 'a'];
+        }
+        for (const auto& sticker_count : sticker_counts) {
+            if (sticker_count[target[0] - 'a'] == 0) {
+                continue; 
+            }
+            string new_target;
+            for (int i = 0; i < target_count.size(); ++i) {
+                if (target_count[i] - sticker_count[i] > 0) {
+                    new_target += string(target_count[i] - sticker_count[i], 'a' + i);
+                }
+            }
+            if (new_target.length() != target.length()) {
+                int num = minStickersHelper(sticker_counts, new_target, dp);
+                if (num != -1) {
+                    result = min(result, 1 + num);
+                }
+            }
+        }
+        (*dp)[target] = (result == numeric_limits<int>::max()) ? -1 : result;
+        return (*dp)[target];
+    }
+};
