2707. Extra Characters in a String

class Solution {
public:
    vector<int> ans;
    unordered_map<string, bool> mp;

    int minExtraChar(string s, vector<string>& dictionary) {
        ans.resize(s.size()+1, 0x3f3f3f3f);    
        for(string a : dictionary) mp[a] = true;
        ans[s.size() - 1] = !mp[string(1, s.back())];
        ans[s.size()] = 0;
        
        for(int i = s.size() - 2; i >= 0; --i){
            for(int j = 1; j <= s.size() - i; ++j) {
                string tmp = s.substr(i, j);
                ans[i] = min(ans[i], (mp[tmp]?0:j) + ans[i+j]);
            }
        }
        return ans[0];
    }
};