Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-07-25

WordParts

| 09:31

問題文

問題文が短く、問題の意味は理解できたが、解法が思いつかず、Editorialを見た。メモ化か。慣れない。

class WordParts {
public:
    int partCount(string original, string compound) {
        const int ori_len = original.length();
        len = compound.length();
        dict.clear();
        dict.insert(original);
        for (int i = 1; i < ori_len; i++) {
            dict.insert(original.substr(0,ori_len-i));
            dict.insert(original.substr(ori_len-i));
        }
        memo = vector<int>(len, -1);
        const int parts = minParts(compound, 0);
        if (parts >= INFTY) return -1;
        else return parts;
    }
private:
    int len;
    set<string> dict;
    vector<int> memo;
    const static int INFTY = INT_MAX/2;
    int minParts(const string& compound, const int pos) {
        if (pos == len) return 0;
        if (memo[pos] != -1) return memo[pos];
        memo[pos] = INFTY;
        for (set<string>::const_iterator w = dict.begin();
                    w != dict.end(); w++) {
            const int w_len = (*w).length();
            if (*w == compound.substr(pos, w_len))
                memo[pos] = min(memo[pos], 1+minParts(compound,pos+w_len));
        }
        return memo[pos];
    }
};