C++ DP solution with explanation


  • 0
    G
    // So the idea here is copied from the rest of the solutions:
        // DP[target_string] = MIN_For_All_Stickers(1 + DP[string_without_sticker_applied])
        // Then the tricky thing is to solve the sub-problem here, how do we even
        // represent the sub problem.
        // 1) We can have a mask to represent which characters in the target string are still pending.
        //   example target: "Test", initially the mask will be 15 (1111), i.e. all strings have to be matched.
        //   Then once lets say 'e' gets matched, we are left with "T_st" and mask will be 11 (1011).
        //   and so on...Base case will be mask = 0, where solution will be 0.
        // 2) To represent the sub problems we can also use actual strings around, i.e. "test", "tst" etc.
        //    A good solution had these in the sorted way, i.e "estt" and "stt", etc.
        int helper(vector<string>& stickers, string& target, unordered_map<int, int>& cache, int mask) {
            if (!mask) { return 0; } // If mask == 0, return 0;
            
            auto it = cache.find(mask);
            if (it != cache.end()) {
                return (*it).second; 
            }
            
            int N = target.size();
            int result = INT_MAX;
            for (string s : stickers) {
                int new_mask = mask;
                for (char c : s) {
                    for (int i=0; i < N; ++i) {
                        // Check if a character in sticker matches a not-yet matched char in target.
                        if (target[i] == c && ((new_mask >> (N - i - 1)) & 1)) {
                            new_mask &= ~(1 << (N-i-1));
                            break; // This is important, otherwise one character can be matched to many in target.
                        }
                    }
                }
                if (new_mask != mask) {
                    int sub_problem_result = helper(stickers, target, cache, new_mask);
                    if (sub_problem_result == -1) { cache[mask] = -1; return -1; }
                    
                    result = min(result, 1 + sub_problem_result);
                }
            }
            cache[mask] = result == INT_MAX ? -1 : result;
            return cache[mask];
        }
        
        int minStickers(vector<string>& stickers, string target) {
            int mask = (1 << target.size()) - 1;
            unordered_map<int, int> result;
            return helper(stickers, target, result, mask);
        }
    

Log in to reply
 

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