Re: [閒聊] 每日leetcode
看板Marginalman作者enmeitiryous (enmeitiryous)時間1年前 (2024/09/24 00:19)推噓0(0推 0噓 0→)留言0則, 0人參與討論串898/1554 (看更多)
作業兩天進度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()];
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.227.252.3 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1727108399.A.54A.html
討論串 (同標題文章)
完整討論串 (本文為第 898 之 1554 篇)：