[LeetCode]Stickers to Spell Word

题目描述:

LeetCode 691. Stickers to Spell Word

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 string 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.

What is the minimum number of stickers that you need to spell out the target? If the task is impossible, return -1.

Example 1:

Input:

["with", "example", "science"], "thehat"

Output:

3

Explanation:

We can use 2 "with" stickers, and 1 "example" sticker.
After cutting and rearrange the letters of those stickers, we can form the target "thehat".
Also, this is the minimum number of stickers necessary to form the target string.

Example 2:

Input:

["notice", "possible"], "basicbasic"

Output:

-1

Explanation:

We can't form the target "basicbasic" from cutting letters from the given stickers.

Note:

  • stickers has length in the range [1, 50].
  • stickers consists of lowercase English words (without apostrophes).
  • target has length in the range [1, 15], and consists of lowercase English letters.
  • In all test cases, all words were chosen randomly from the 1000 most common US English words, and the target was chosen as a concatenation of two random words.
  • The time limit may be more challenging than usual. It is expected that a 50 sticker test case can be solved within 35ms on average.

题目大意:

给定一组单词stickers,目标单词target。利用stickers中的字母组成target,每个stickers的单词可以重复多次,求最小需要的stickers的单词个数。

解题思路:

解法I 记忆化搜索(Search + Memoization)

Python代码:

class Solution(object):
    def minStickers(self, stickers, target):
        """
        :type stickers: List[str]
        :type target: str
        :rtype: int
        """
        cntToStr = lambda cnt: ''.join(sorted(k * v for k, v in cnt.iteritems()))
        tcnt = collections.Counter(target)
        scnts = [collections.Counter(s) & tcnt for s in stickers]
        for x in range(len(scnts) - 1, -1, -1):
            if any(scnts[x] & scnts[y] == scnts[x] for y in range(len(scnts) - 1, -1, -1) if x != y):
                scnts.pop(x)
        stickers = map(cntToStr, scnts)
        sset = set(stickers)
        dmap = {}
        def search(kcnt):
            key = cntToStr(kcnt)
            if not key: return 0
            if key in sset: return 1
            if key in dmap: return dmap[key]
            ans = -1
            for scnt in scnts:
                nkcnt = collections.Counter(kcnt)
                for k in scnt:
                    if nkcnt[k]: nkcnt[k] -= scnt[k]
                    if nkcnt[k] <= 0: del nkcnt[k]
                if nkcnt == kcnt: continue
                val = search(nkcnt)
                if val < 0: continue
                if ans < 0 or val + 1 < ans: ans = val + 1
            dmap[key] = ans
            return ans
        return search(tcnt)

Java代码:

class Solution {
    private HashMap<String, Integer> dmap;
    private HashMap<String, int[]> scnts;
    
    public int[] str2Cnt(String str) {
        int[] cnt = new int[26];
        for (int i = 0; i < str.length(); i++) {
            cnt[str.charAt(i) - 'a']++;
        }
        return cnt;
    }
    
    public String cnt2Str(int[] cnt) {
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < cnt[i]; j++) {
                sb.append('a' + i);
            }
        }
        return sb.toString();
    }
    
    public int minStickers(String[] stickers, String target) {
        dmap = new HashMap<>();
        scnts = new HashMap<>();
        int[] tcnt = str2Cnt(target);
        for (int i = 0; i < stickers.length; i++) {
            StringBuffer sb = new StringBuffer();
            for (int j = 0; j < stickers[i].length(); j++) {
                char ch = stickers[i].charAt(j);
                if (tcnt[ch - 'a'] > 0) sb.append(ch);
            }
            String str = sb.toString();
            if (str.length() > 0 && !scnts.containsKey(str)) {
                scnts.put(str, str2Cnt(str));
            }
        }
        return search(tcnt);
    }

    public int search(int[] kcnt) {
        String key = cnt2Str(kcnt);
        if (key.length() == 0) return 0;
        if (scnts.keySet().contains(key)) return 1;
        if (dmap.containsKey(key)) return dmap.get(key);
        int ans = -1;
        for (int[] scnt : scnts.values()) {
            int[] nkcnt = kcnt.clone();
            boolean stopFlag = true;
            for (int i = 0; i < 26; i++) {
                int nval = Math.max(0, nkcnt[i] - scnt[i]);
                if (nval != nkcnt[i]) stopFlag = false;
                nkcnt[i] = nval;
            }
            if (stopFlag) continue;
            int val = search(nkcnt);
            if (val < 0) continue;
            if (ans < 0 || val + 1 < ans) ans = val + 1;
        }
        dmap.put(key, ans);
        return ans;
    }

}

解法II 动态规划(Dynamic Programming)

Python代码:

class Solution(object):
    def minStickers(self, stickers, target):
        """
        :type stickers: List[str]
        :type target: str
        :rtype: int
        """
        dp = [0] + [-1] * ((1 <<  len(target)) - 1)
        tcnt = collections.Counter(target)
        scnts = [collections.Counter(s) & tcnt for s in stickers]
        for x in range(len(scnts) - 1, -1, -1):
            if any(scnts[x] & scnts[y] == scnts[x] for y in range(len(scnts) - 1, -1, -1) if x != y):
                scnts.pop(x)
        for status in range(1 << len(target)):
            if dp[status] < 0: continue
            for scnt in scnts:
                nstatus = status
                cnt = collections.Counter(scnt)
                for i, c in enumerate(target):
                    if cnt[c] > 0 and status & (1 << i) == 0:
                        nstatus |= (1 << i)
                        cnt[c] -= 1
                if dp[nstatus] < 0 or dp[nstatus] > dp[status] + 1:
                    dp[nstatus] = dp[status] + 1
        return dp[-1]

 

本文链接:http://bookshadow.com/weblog/2017/10/08/leetcode-stickers-to-spell-word/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码