verbose DFS+MEMO solution, C++


  • 0
    J

    My solution is a basic dfs + memo one.
    And I applied string to represent the situation to be hashed.
    For example, if we have string "thehat", then I'll record that as "a1e1h2t2", each char followed by its occurrence, in lexicographical order.
    The base case comes for stirng "", where we have value 0;

        unordered_map<string,int> mp;
     
        // for string like "thehat", it will become "a1e1h2t2"
        string transfer(vector<int> &hash){             
            string res = "";
            for(int i = 0; i < 26; ++i){
                if(hash[i] > 0){
                    res.insert(res.end(), 'a' + i);
                    res += to_string(hash[i]);
                }
            }
            return res;
        }
        
        // dfs + memo
        int helper(vector<string>& stickers, vector<int> & hash){
            string cur = transfer(hash);
            if(mp.find(cur) != mp.end()) return mp[cur];
            int minNum = INT_MAX;
            for(string &s : stickers){
                bool flag = false;
                for(char &c : s){
                    if(hash[c-'a'] > 0) flag = true;        // this sticker make sense
                    hash[c-'a']--;
                }
                if(flag)    minNum = min(minNum, helper(stickers, hash));
                for(char &c : s) hash[c-'a']++;             // backtracking, recover
            }
            return mp[cur] = 1 + minNum;
        }
    
        
        int minStickers(vector<string>& stickers, string target) {
            mp.insert({"",0});
            unordered_set<char> rec;
            vector<int> hash(26,0);
            for(char &c : target){
                rec.insert(c);
                hash[c-'a']++;
            }
            // check possible or not
            for(string &s :stickers){
                for(char &c : s)
                    if(rec.count(c)) rec.erase(c);
            }
            if(rec.size() > 0) return -1;
            return helper(stickers, hash);
        }
    

    The code here is kind of ugly because the tight time for contest. The running time is 500+ms.

    1. I use a bool value to check whether applying certain sticker could make up for some remaining chars, not just decrease the count for some non-positive slots.
    2. To handle situation of returning -1, I use an extra set.

    Any good advice? Thank you!


Log in to reply
 

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