6394. 字符串中的额外字符
使用动态规划求解
详见代码：
class Solution {
public:
int minExtraChar(string s, vector<string>& ct) {
int n=s.size();
vector<int> dp(n+1,n);
dp[0]=0;
for(int i=0;i<n;++i){
for(auto a:ct){
if(s.substr(i,a.size())==a){
dp[i+a.size()]=min(dp[i+a.size()],dp[i]);//以匹配上的字符串转移状态
}
}
dp[i+1]=min(dp[i+1],dp[i]+1);//假设当前位置无法匹配字典中的字符串
}
return dp[n];
}
};