C++/Java/Python, DP + Memoization with optimization, 29 ms (C++)


  • 31
    Z

    There are potentially a lot of overlapping sub problems, but meanwhile we don't exactly know what those sub problems are. DP with memoization works pretty well in such cases. The workflow is like backtracking, but with memoization. Here I simply use a sorted string of target as the key for the unordered_map DP. A sorted target results in a unique sub problem for possibly different strings.

    dp[s] is the minimum stickers required for string s (-1 if impossible). Note s is sorted.
    clearly, dp[""] = 0, and the problem asks for dp[target].
    

    The DP formula is:

    dp[s] = min(1+dp[reduced_s]) for all stickers, 
    here reduced_s is a new string after certain sticker applied
    

    Optimization: If the target can be spelled out by a group of stickers, at least one of them has to contain character target[0]. So I explicitly require next sticker containing target[0], which significantly reduced the search space.

    BTW, I am not good at Java. Looking forward to your revision!

    C++

    class Solution {
    public:
        int minStickers(vector<string>& stickers, string target) {
            int m = stickers.size();
            vector<vector<int>> mp(m, vector<int>(26, 0));
            unordered_map<string, int> dp;
            // count characters a-z for each sticker 
            for (int i = 0; i < m; i++) 
                for (char c:stickers[i]) mp[i][c-'a']++;
            dp[""] = 0;
            return helper(dp, mp, target);
        }
    private:
        int helper(unordered_map<string, int>& dp, vector<vector<int>>& mp, string target) {
            if (dp.count(target)) return dp[target];
            int ans = INT_MAX, n = mp.size();
            vector<int> tar(26, 0);
            for (char c:target) tar[c-'a']++;
            // try every sticker
            for (int i = 0; i < n; i++) {
                // optimization
                if (mp[i][target[0]-'a'] == 0) continue; 
                string s;
                // apply a sticker on every character a-z
                for (int j = 0; j < 26; j++) 
                    if (tar[j]-mp[i][j] > 0) s += string(tar[j]-mp[i][j], 'a'+j);
                int tmp = helper(dp, mp, s);
                if (tmp!= -1) ans = min(ans, 1+tmp);
            }
            dp[target] = ans == INT_MAX? -1:ans;
            return dp[target];
        }
    };
    

    Java

    class Solution {
        public int minStickers(String[] stickers, String target) {
            int m = stickers.length;
            int[][] mp = new int[m][26];
            Map<String, Integer> dp = new HashMap<>();
            for (int i = 0; i < m; i++) 
                for (char c:stickers[i].toCharArray()) mp[i][c-'a']++;
            dp.put("", 0);
            return helper(dp, mp, target);
        }
        private int helper(Map<String, Integer> dp, int[][] mp, String target) {
            if (dp.containsKey(target)) return dp.get(target);
            int ans = Integer.MAX_VALUE, n = mp.length;
            int[] tar = new int[26];
            for (char c:target.toCharArray()) tar[c-'a']++;
            // try every sticker
            for (int i = 0; i < n; i++) {
                // optimization
                if (mp[i][target.charAt(0)-'a'] == 0) continue;
                StringBuilder sb = new StringBuilder();
                // apply a sticker on every character a-z
                for (int j = 0; j < 26; j++) {
                    if (tar[j] > 0 ) 
                        for (int k = 0; k < Math.max(0, tar[j]-mp[i][j]); k++)
                            sb.append((char)('a'+j));
                }
                String s = sb.toString();
                int tmp = helper(dp, mp, s);
                if (tmp != -1) ans = Math.min(ans, 1+tmp);
            }
            dp.put(target, ans == Integer.MAX_VALUE? -1:ans);
            return dp.get(target);
        }
    }
    

    Python

    class Solution(object):
        def minStickers(self, stickers, target):
            m = len(stickers)
            mp = [[0]*26 for y in range(m)] 
            for i in range(m):
                for c in stickers[i]:
                    mp[i][ord(c)-ord('a')] += 1    
            dp = {}
            dp[""] = 0
            
            def helper(dp, mp, target):
                if target in dp:
                    return dp[target]
                n = len(mp)
                tar = [0]*26
                for c in target:
                    tar[ord(c)-ord('a')] += 1   
                ans = sys.maxint
                for i in xrange(n):
                    if mp[i][ord(target[0])-ord('a')] == 0:
                        continue
                    s = ''
                    for j in range(26):
                        if tar[j] > mp[i][j]:
                            s += chr(ord('a')+j)*(tar[j] - mp[i][j]) 
                    tmp = helper(dp, mp, s)
                    if (tmp != -1): 
                        ans = min(ans, 1+tmp)    
                dp[target] = -1 if ans == sys.maxint else ans
                return dp[target]
                    
            return helper(dp, mp, target)
    

  • 0
    A

    Same solution in Python:

    class Solution(object):
        def minStickers(self, stickers, target):
            m = len(stickers)
            mp = [collections.Counter(s) for s in stickers]
            dp = collections.defaultdict(int)
            dp[""] = 0
            def helper(dp, mp, target):
                if target in dp:
                    return dp[target]
                
                n = len(mp)
                tar = collections.Counter(target)
                ans = sys.maxint
                for i in xrange(n):
                   if target[0] not in mp[i]:
                        continue
                    s = ''
                    for t in tar:
                        s += t*max(0, tar[t] - mp[i][t]) if t in mp[i] else t*tar[t]
                    
                    if len(s) != len(target):
                        tmp = helper(dp, mp, s)
                        if (tmp != -1): 
                            ans = min(ans, 1+tmp)
                            
                dp[target] = -1 if ans == sys.maxint else ans
                return dp[target]
                    
            return helper(dp, mp, target)

  • 1
    Z

    @Aimar88 I attached a working Python. Check it out.


  • 1
    J

    Nice code.
    BTW, I tried to delete the optimization line, and it yields a running time of 532ms.
    So I was kind of shocked by how amazing this line of code was...


  • 0
    A

    I justed added the optimization line and got accepted!

    if target[0] not in mp[i]:
        continue

  • 3
    Z

    @JadenPan You can imagine backtracking is a growing multi children tree, and that line limits the number of children by certain percent. For example, a 10 children tree vs 5 children tree.


  • 0
    W

    @zestypanda I could not figure out the time complexity of your code. Do you have any idea about O( ) ? Thanks,


  • 0
    Z

    @wwzzgg O(2^m 26n) where m is length of target, n is number of stickers.
    2^m is number of sub target in worst case, and m <= 15, n <= 50, so 2^m < 32000;


  • 2
    I

    @zestypanda Nice solution and good optimization!
    Btw, in your code, you don't need this if (s.length() != target.length()) extra check. Since your optimization code if (mp[i][target.charAt(0)-'a'] == 0) continue; will make sure the new string s will always be different from target.


  • 0
    Z

    @ihaveayaya Thanks!


  • 0

    @zestypanda nice solution.
    However, for the optimization:
    if (mp[i][target[0]-'a'] == 0) continue;
    I guess the string should be sorted to do that.
    Of course the string is sorted after the first step. But in the minStickers function, should we add
    sort(target.begin(), target.end());
    before the last line?


  • 1
    Z

    @Victor_FW No, you don't have to. The goal of sorting is uniqueness. The initial string is unique.


  • 0
    R

    @zestypanda Math.max(0, tar[j]-mp[i][j]) checking for max is not required. just tar[j]-mp[i][j] is enough.


  • 0
    R

    @zestypanda
    Wondering how you came up with the optimization. What is the thought behind it?
    That single line makes the code run extremely fast.
    In my code I used :

                if(s.equals(target))
                    continue;
    

    as a terminating condition.
    This is very slow.


  • 0
    J

    @zestypanda

    if (tar[j]-mp[i][j] > 0) s += string(tar[j]-mp[i][j], 'a'+j);
    

    Should it be > or >= for the if statement?


  • 0
    C

    @jtee no diff


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.