WordParts

TopCoder: WordParts –> Editorial

• prefix, suffix
  
• memoization
  

d[i][j] = min(d[i][k] + d[k+1][j])
          k --- substring(i,k) exists in the prefix/suffix array

set<string> dict;
#define INF 999999999
int memo[51];

void checkmin(int &a, int b) {
   if (b < a) a = b;
}
int solve(string &compound, int cpos) {
   //cout << compound.substr(cpos) << " " << cpos << endl;
   if(memo[cpos] >= 0) return memo[cpos];
   if(cpos == compound.length()) return memo[cpos] = 0;

   int res = INF;
   int maxlen = compound.length() - cpos;

   for(int i = 1; i <= maxlen; ++i) {
       string s = compound.substr(cpos, i);      
       if(dict.count(s)) {
           checkmin(res, 1+solve(compound, cpos+i));
       }
   }
   return memo[cpos] = res;
}  

int WordParts::partCount(string original, string compound) {
   dict.clear(); // don’t forget to reset dict
   // add the whole word
   dict.insert(original);
   // add all prefix
   for(int i = 1; i <= original.length()-1; ++i)
       dict.insert(original.substr(0,i));
   // add all suffix
   for(int i = 1; i <= original.length()-1; ++i)
       dict.insert(original.substr(i));

   memset(memo, -1, sizeof(memo));
   int res = solve(compound, 0);
   if(res == INF) return -1;
   return res;
}