class Solution {
public:
int minExtraChar(string s, vector<string>& dictionary) {
unordered_set<string> hash(dictionary.begin(), dictionary.end());
int n = s.size();
int f[n + 1];
f[0] = 0;
for (int i = 1; i <= n; i ++ ) {
f[i] = f[i - 1] + 1;
for (int j = 0; j < i; j ++ )//因为字符串下标从0开始,所以是[j, i - 1]
if (hash.count(s.substr(j, i - j)))
f[i] = min(f[i], f[j]);
}
return f[n];
}
};