作业两天进度0 死去
题目2707. Extra Characters in a String
给你一个字串s和一个vector的字串组，求你用字串组中的字串尽可能组合成s所需要的
最少补上char数
思路:
可以用DP，dp[i]是从0到i需要补的字母数，确认当前字首并一遍遍确定之后一定长度len
的子字串有没有出现在字串组中，有的话则更新dp[i+len]=min(dp[i+len],dp[i]-len)，
如果都没有找到符合子字串或是该字首根本没有出现在字串组则dp[i]=min(dp[i],dp[i-1]
最后回传dp[n]
复杂度算起来是n**3，但因为n<50所以DP和理论题目希望的trie解法速度差不多(n**2)但
只要n一增加就会像昨天和前天题目一样相比下限定只能用trie作法
int minExtraChar(string s, vector<string>& dictionary) {
vector<int> pre_ans(s.size()+1,s.size());
map<char,set<string>> dom;
unordered_map<char,int> domlim;
for(int i=0;i<dictionary.size();++i){
dom[dictionary[i][0]].insert(dictionary[i]);
if(!domlim.count(dictionary[i][0])){
domlim[dictionary[i][0]]=dictionary[i].size();
}
else{
domlim[dictionary[i][0]]=max((int)dictionary[i].size(),domlim[dictionary[i][0]]);
}
}
for(int i=1;i<s.size()+1;++i){
if(domlim.count(s[i-1])){
int gh=min((int)s.size()-i+1,domlim[s[i-1]]);
for(auto k:dom[s[i-1]]){
if(k.size()<=gh && s.substr(i-1,k.size())==k){
pre_ans[i-1+k.size()]=min((int)pre_ans[i-1+k.size()],(int)(pre_ans[i-1]-k.size()));
}
}
pre_ans[i]=min(pre_ans[i],pre_ans[i-1]);
}
else{
pre_ans[i]=min(pre_ans[i-1],pre_ans[i]);
}
}
return pre_ans[s.size()];
}