作者推荐
本文涉及知识点
动态规划汇总 字典树
LeetCode472 连接词
给你一个 不含重复 单词的字符串数组 words ，请你找出并返回 words 中的所有 连接词 。
连接词 定义为：一个完全由给定数组中的至少两个较短单词（不一定是不同的两个单词）组成的字符串。
示例 1：
输入：words = [“cat”,“cats”,“catsdogcats”,“dog”,“dogcatsdog”,“hippopotamuses”,“rat”,“ratcatdogcat”]
输出：[“catsdogcats”,“dogcatsdog”,“ratcatdogcat”]
解释：“catsdogcats” 由 “cats”, “dog” 和 “cats” 组成;
“dogcatsdog” 由 “dog”, “cats” 和 “dog” 组成;
“ratcatdogcat” 由 “rat”, “cat”, “dog” 和 “cat” 组成。
示例 2：
输入：words = [“cat”,“dog”,“catdog”]
输出：[“catdog”]
提示：
1 <= words.length <= 104
1 <= words[i].length <= 30
words[i] 仅由小写英文字母组成。
words 中的所有字符串都是 唯一 的。
1 <= sum(words[i].length) <= 105
动态规划+字典树
分以下几步：
一，将所有单词存到字典树中。
二，枚举各单词s=word[i]，如果s[0,j)是字典树的叶子节点，则将j放到dp[i]中。
三，对dp[i]排序，出掉重复。
四，交换pre,dp。
五，如果pre[i]存在words[i].length，删除之。
六，循环处理pre，直到pre[i]全部为空。
七, for(j ;pre[i]) 如果字典树中存在words[i][j,k)且是叶子节点。将k加到dp[i]中。
八，对dp[i]排序，出掉重复。
九，交换pre,dp。
十,如果pre[i]存在wrods[i].length，将words[i]放到结果中，并清空pre[i]。
封装的字典树
template<class TData=char, int iTypeNum = 26, TData cBegin = 'a'> class CTrieNode { public: CTrieNode* AddChar(TData ele,int& iMaxID) { #ifdef _DEBUG if ((ele < cBegin) || (ele >= cBegin + iTypeNum)) { return nullptr; } #endif const int index = ele - cBegin; auto ptr = m_vPChilds[ele - cBegin]; if (!ptr) { m_vPChilds[index] = new CTrieNode(); #ifdef _DEBUG m_vPChilds[index]->m_iID = ++iMaxID; m_childForDebug[ele] = m_vPChilds[index]; #endif } return m_vPChilds[index]; } CTrieNode* GetChild(TData ele)const { #ifdef _DEBUG if ((ele < cBegin) || (ele >= cBegin + iTypeNum)) { return nullptr; } #endif return m_vPChilds[ele - cBegin]; } protected: #ifdef _DEBUG int m_iID = -1; std::unordered_map<TData, CTrieNode*> m_childForDebug; #endif public: int m_iLeafIndex = -1; protected: CTrieNode* m_vPChilds[iTypeNum] = { nullptr }; }; template<class TData = char,int iTypeNum = 26, TData cBegin = 'a'> class CTrie { public: int GetLeadCount() { return m_iLeafCount; } template<class IT> int Add(IT begin, IT end) { auto pNode = &m_root; for (; begin != end; ++begin) { pNode = pNode->AddChar(*begin,m_iMaxID); } if (-1 == pNode->m_iLeafIndex) { pNode->m_iLeafIndex = m_iLeafCount++; } return pNode->m_iLeafIndex; } template<class IT> CTrieNode<TData, iTypeNum, cBegin>* Search(IT begin, IT end) { auto ptr = &m_root; for (; begin != end; ++begin) { ptr = ptr->GetChild(begin); if (nullptr == ptr) { return nullptr; } } return ptr; } CTrieNode<TData, iTypeNum, cBegin> m_root; protected: int m_iMaxID = 0; int m_iLeafCount = 0; };
核心代码
class Solution { public: vector<string> findAllConcatenatedWordsInADict(vector<string>& words) { CTrie preTrie; for (const auto& s : words) { preTrie.Add(s.begin(), s.end()); } vector<vector<int>> pre(words.size(),vector<int>(1)); auto Do = [&]() { vector<vector<int>> dp(words.size()); for (int i = 0; i < pre.size(); i++) { for (const auto& j : pre[i]) { auto p1 = &preTrie.m_root; for (int k = j; k < words[i].length(); k++) { p1 = p1->GetChild(words[i][k]); if (nullptr == p1) { break; } if (-1 != p1->m_iLeafIndex) { dp[i].emplace_back(k + 1); } } } sort(dp[i].begin(), dp[i].end()); dp[i].erase(std::unique(dp[i].begin(), dp[i].end()), dp[i].end()); } pre.swap(dp); }; Do(); for (int i = 0 ; i < pre.size(); i++ ) { if (pre[i].size() && (pre[i].back() == words[i].length())) { pre[i].pop_back(); } } vector<string> vRet; bool bDo = true; while (bDo) { Do(); bDo = false; for (int i = 0; i < pre.size(); i++) { if (pre[i].size()) { bDo = true; } if (pre[i].size() && (pre[i].back() == words[i].length())) { vRet.emplace_back(words[i]); pre[i].clear(); } } } return vRet; } };
测试用例
template<class T> void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { vector<string> words; { Solution sln; words = { "cat","dog","catdog" }; auto res = sln.findAllConcatenatedWordsInADict(words); Assert(vector<string>{"catdog"}, res); } { Solution sln; words = { "cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat" }; auto res = sln.findAllConcatenatedWordsInADict(words); Assert(vector<string>{"catsdogcats", "dogcatsdog", "ratcatdogcat"}, res); } { Solution sln; words = { "vhsgzvwiixxaob","fso","qnebmfl","ooetjiz","lq","msxphqdgz","mqhoggvrvjqrp","xbhkkfg","zxjegsyovdrmw","jav","mshoj","ax","biztkfomz","hujdmcyxdqteqja","gqgsomonv","reqqzzpw","lihdnvud","lznfhbaokxvce","fhxbldylqqewdnj","rlbskqgfvn","lfvobeyolyy","v","iwh","fpbuiujlolnjl","gvwxljbo","ypaotdzjxxrsc","mwrvel","umzpnoiei","ogwilaswn","yw","egdgye","hsrznlzrf","mwdgxaigmxpy","yaqgault","dtlg","cyvfiykmkllf","zxqyhvizqmamj","lvvgoifltzywueyp","abinmy","ppzaecvmx","qsmzc","iddymnl","uskihek","evxtehxtbthq","jvtfzddlgch","czohpyewf","ufzazyxtqxcu","brxpfymuvfvs","xrrcfuusicc","aqhlswbzievij","rv","udvmara","upityz","fecd","suxteeitxtg","dfuydrtbfypbn","cypqodxr","wikfuxwjht","jrliuaifpp","vkmxys","wvpfyfpkvgthq","rmajxis","jncxgviyu","av","nmhskodmidaj","lkfrimprrhen","uip","hstyopbvuiqc","p","vwduwmjpblqo","fnxwgqtvwztje","xwnbcuggl","iehimvoymyjasin","spsqiu","flhyfac","mqrbq","pstsxhplrrmbeddv","hnegtuxx","alsyxezjwtlwmxv","jtxytykkcku","bhhlovgcx","xhhivxnutkx","had","aysulvk","m","anhsyxli","jdkgfc","potn","lcibpxkidmwexp","gwoxjicdkv","tltienw","ngiutnuqbzi","o","tzlyb","vumnwehj","os","np","lhv","uzvgyeette","ipfvr","lpprjjalchhhcmh","k","pciulccqssaqgd","tp","dmzdzveslyjad","wtsbhgkd","eouxbldsxzm","vhtonlampljgzyve","xhnlcrldtfthul","xhflc","upgei","rlaks","yfqvnvtnqspyjbxr","phouoyhvls","voibuvbhhjcdflvl","rgorfbjrofokggaf","dqhqats","zchpicyuawpovm","yzwfor","koat","pybf","fhdzsbiyjld","gznfnqydisn","xz","po","tcjup","wygsnxk","kqlima","fgxnuohrnhg","publurhztntgmimc","zuufzphd","iucrmmmjqtcey","wnnbq","rghzyz","ukjqsjbmp","mdtrgv","vyeikgjdnml","kxwldnmi","apzuhsbssaxj","tkbkoljyodlipof","nkq","ktwtj","vgmkgjwle","t","agylw","vomtuy","jbtvitkqn","vtdxwrclpspcn","rdrls","yxfeoh","upj","myctacn","fdnor","ahqghzhoqprgkym","phiuvdv","jp","fdgpouzjwbq","hqoyefmugjvewhxu","qfzwuwe","fnsbijkeepyxry","oja","qthkcij","zpmqfbmnr","ybaibmzonzqlnmd","svo","gjftyfehik","jfrfgznuaytvaegm","aljhrx","odjq","ogwaxrssjxgvnka","zaqswwofedxj","lugpktauixp","dc","odknlbvxrs","jeobu","vqythyvzxbcgrlbg","hwc","erpbaxq","ujxcxck","rrklkb","wlrwyuy","zmg","yyhga","xwdbycdu","htedgvsrhchox","wr","suhesetv","jonqwhkwezjvjgg","sqqyrxtjkcalswq","hvyimhe","pjzdkmoue","zbphmgoxq","lbdlcumdgixjbcq","ztzdjqmadthtdmv","qcagsyqggcf","if","jpjxcjyi","chyicqibxdgkqtg","iwpdklhum","wljmg","micmun","npdbamofynykqv","ijsnfkpfy","lmq","oyjmeqvhcrvgm","mqopusqktdthpvz","fz","r","qbsqtipq","nxtsnason","xbpipyhh","topsuqomfjrd","islif","gbndakaq","bwnkxnwpzeoohlx","hrtbfnq","fguvomeepxoffg","mat","dzfpfnwbfuj","onlvy","cwcchvsasdylb","rxfcztzqopdi","ybrhodjn","oqkijy","ncvrjo","dphbfaal","xgtpdtkz","sebevsopjvciwljf","rcumyacqdapwczen","mabkapuoud","pbozezeygljfftvy","bvazmzbndl","vl","qiaixdtbhqvlzd","ffjfb","svthrfmkoxbho","cvet","ucgqyvopafyttrh","lbgihet","naiqyufxffdw","vruh","uz","ukffmudygjavem","dccamymhp","wofwgjkykm","fbuujzxhln","kmm","lzandlltowjpwsal","fapfvrmezbsjxs","wiw","sc","soqlh","hzaplclkwl","gcdqbcdwbwa","gadgt","pgowefka","juffuguqepwnfh","nbuinl","cpdxf","sox","fq","lfnrhgsxkhx","xrcorfygjxpi","mwtqjwbhgh","loc","fkglorkkvx","nlzdhucvayrz","azefobxutitrf","rlrstkcbtikklmh","ggk","sbphcejuylh","nraoenhd","zngyodiqlchxyycx","rrbhfwohfv","krzolrglgn","cpjesdzy","yoifoyg","hqqevqjugi","ahmv","xgaujnyclcjq","evhyfnlohavrj","byyvhgh","hyw","kedhvwy","ysljsqminajfipds","rglnpxfqwu","cibpynkxg","su","mbntqrlwyampdg","nig","ldhlhqdyjcfhu","jfymrbafmyoc","tyjmnhlfnrtz","dlazixtlxyvm","fbiguhsfuqo","rhymsno","rkbdlchs","ocbbwwd","astaiamnepwkya","mplirup","edkxjq","g","exlwulswtvot","tlnc","vnrrzerz","ygeraoozbtt","yyifkin","eo","ua","qgztvqdolf","rlzddjzcshvd","khxkdxflwxme","kk","zylbhoaac","cw","iizic","gcdxstpz","kjwdqeg","earjrncmmkdel","kbesuhquepj","nrzbllldgdmyrpgl","hllwnqozf","djpchowhwevbqvjj","zsmhylnjpktb","pxnktxkm","fxwiaqqb","qjwufmwresfsfaok","aa","d","iobioqm","svjgzk","khbzp","euexyudhrioi","yqsj","ngrwqpoh","rwuvd","eruffmlg","bxzovyew","faz","pmvfvyguqdi","jlxnoixsy","hyfrdngjf","ly","eibcapetpmeaid","tpnwwiif","pfgsp","kvhhwkzvtvlhhb","pjxurgqbtldims","rncplkeweoirje","akyprzzphew","wyvfpjyglzrmhfqp","ubheeqt","rmbxlcmn","taqakgim","apsbu","khwnykughmwrlk","vtdlzwpbhcsbvjno","tffmjggrmyil","schgwrrzt","mvndmua","nlwpw","glvbtkegzjs","piwllpgnlpcnezqs","xkelind","urtxsezrwz","zechoc","vfaimxrqnyiq","ybugjsblhzfravzn","btgcpqwovwp","zgxgodlhmix","sfzdknoxzassc","wgzvqkxuqrsqxs","dwneyqisozq","fg","vhfsf","uspujvqhydw","eadosqafyxbmzgr","tyff","blolplosqnfcwx","uwkl","puenodlvotb","iizudxqjvfnky","cjcywjkfvukvveq","jrxd","igwb","dftdyelydzyummmt","uvfmaicednym","oai","higfkfavgeemcgo","naefganqo","iqebfibigljbc","ulicojzjfrc","igxprunj","cymbrl","fqmwciqtynca","zjyagi","mzuejrttefhdwqc","zyiurxvf","wrjxffzbjexsh","wrxw","mhrbdxjwi","htknfa","wfrvxqdkhbwwef","vqsghhhutdget","cwupzrts","hbjnb","wpccoa","nx","howbzhaoscgyk","bilt","wqqatye","zceuuwg","jxzon","kkfj","bwsezd","ifdegsyjtswselk","xweimxlnzoh","tqthlftjblnpht","ww","ss","b","jmruuqscwjp","nxbk","wd","cqkrtbxgzg","xhppcjnq","cfq","tkkolzcfi","wblxki","ijeglxsvc","kcqjjwcwuhvzydm","gubqavlqffhrzz","hiwxrgftittd","caybc","ncsyjlzlxyyklc","poxcgnexmaajzuha","dhaccuualacyl","mtkewbprs","oncggqvr","sqqoffmwkplsgbrp","ioajuppvqluhbdet","dzwwzaelmo","afumtqugec","wglucmugwqi","zveswrjevfz","nxlbkak","pzcejvxzeoybb","fd","vewj","ivws","zjhudtpqsfc","zcmukotirrxx","zksmx","umofzhhowyftz","zbotrokaxaryxlk","ueolqk","dxmzhoq","zvu","cjl","esfmqgvxwfy","npbep","vbgjtbv","poeugoqynkbfiv","fewjjscjrei","yqssxzsydgllfzmo","urxkwcypctjkabi","wqtldwhjouas","tovdtkr","onzgeyddkqwuhnim","ffxviyvsktqrfa","qujhd","pvcz","hiyjlkxmeplnrvxg","hdykehkefp","vepcxhozpjxtreyn","liguhuxudbnh","f","ordxzm","klgohcmmbukz","yrmooliaobbnlap","dutnbetocxylcey","ywdsjegd","cr","blbxhjsgcuoxmqft","ngzdc","srfyjjumcbxole","dazwzwtdjoyuqeqj","xazjarqgfm","fxyfqbeoktcc","qrsjchxp","iltaqzawhgu","sgenjcfxr","yfikp","dvwhbyumthkiktb","walsx","jyajrkcvysicisab","brdeumb","tviihjwxdcz","dnrrgmem","ydgxlrjzucxyid","cdvdpvjlagwmg","ngnpxjkxims","gvyhnchlimsxc","w","jtizpezjl","qe","rjzv","vhnqvi","qm","iedzqswrsnfmnn","lt","utqfcqyrrwm","wtelvsqrru","fjwrhjcrtbcytn","qmqxceuohpiffaq","rmoybqjjgdyo","pmxttqftypfexlv","tg","qa","iqbqjlnpbf","kgaynkddbzllecd","tccvslp","curkxfoimnw","fvnyqkzlheruxr","iiygnzfov","coqs","oa","eiu","vzemmxtklis","lxu","nrwsjaxzwmh","tdayz","oxbbemejgosgcynf","ykbcn","hesvnctfvdsp","ku","rjhykpadahbhj","at","sxlngbtxmqr","wqrom","qzyabzrco","rbbyklndcqdj","cnsmgmwmpbgjq","krvnaf","qrwfajnfahyqocdb","fnlaozmff","vmoymbmytjvfcgt","cijyy","jdgwjbztl","swmalgbgpaplqgz","hfl","typttkrpfvx","tkzpzrscwbx","bwfqqvjcukjbsg","nxqmxr","x","eyavnz","il","dhthp","eyelg","npsoqsw","reogbmveofvusdsx","jvdrjkhxkq","qzjbrpljwuzpl","czqeevvbvcwh","vzuszqvhlmapty","yu","yldwwgezlqur","vorxwgdtgjilgydq","pknt","bgihl","ckorgrm","ixylxjmlfv","bpoaboylced","zea","igfagitkrext","ipvqq","dmoerc","oqxbypihdv","dtjrrkxro","rexuhucxpi","bvmuyarjwqpcoywa","qwdmfpwvamisns","bhopoqdsref","tmnm","cre","ktrniqwoofoeenbz","vlrfcsftapyujmw","updqikocrdyex","bcxw","eaum","oklsqebuzeziisw","fzgyhvnwjcns","dybjywyaodsyw","lmu","eocfru","ztlbggsuzctoc","ilfzpszgrgj","imqypqo","fump","sjvmsbrcfwretbie","oxpmplpcg","wmqigymr","qevdyd","gmuyytguexnyc","hwialkbjgzc","lmg","gijjy","lplrsxznfkoklxlv","xrbasbznvxas" }; auto res = sln.findAllConcatenatedWordsInADict(words); Assert(vector<string>{"rv", "tp", "koat", "po", "mdtrgv", "wr", "mat", "kmm", "ggk", "kk", "fg", "wrxw", "bilt", "ww", "nxbk", "wd", "fd", "tovdtkr", "ordxzm", "tg", "nxqmxr"}, res); } }
优化
b[j] 表示words[i][0,j) 是否能由一个或多个单词拼接。
Do(j) 的功能： b[j]为true，words[i][j,x)能和那些单词匹配。
Do(0)后，b[s.length()] = 0;是因为至少要拼接两次。
class Solution { public: vector<string> findAllConcatenatedWordsInADict(vector<string>& words) { CTrie preTrie; for (const auto& s : words) { preTrie.Add(s.begin(), s.end()); } int b[31] = { 0 }; vector<string> vRet; for (const auto& s : words) { auto Do = [&](int inx) { auto p1 = &preTrie.m_root; for (int k = inx; k < s.length(); k++) { p1 = p1->GetChild(s[k]); if (nullptr == p1) { break; } if (-1 != p1->m_iLeafIndex) { b[k + 1] = true; } } }; memset(b, 0, sizeof(b)); Do(0); b[s.length()] = 0; for (int i = 1; i < s.length(); i++) { if (b[i]) { Do(i); } } if (b[s.length()]) { vRet.emplace_back(s); } } return vRet; } };
2023年1月
class Solution {
public:
vector findAllConcatenatedWordsInADict(vector& words) {
std::unordered_set setHas;
for (const auto& s : words)
{
setHas.insert(s);
}
vector vRet;
for (const auto& s : words)
{
if (Test(s, setHas))
{
vRet.push_back(s);
}
}
return vRet;
}
bool Test(const string& s, const std::unordered_set& setHas)
{
std::vector preLens;
preLens.push_back(0);
while (preLens.size())
{
std::vector lens;
for (const auto& pos : preLens)
{
for (int len = 1; pos + len - 1 < s.length(); len++)
{
if (setHas.count(s.substr(pos, len)))
{
if ((0 == pos) && (s.length() == len))
{
continue;
}
if (pos + len == s.length())
{
return true;
}
lens.push_back(pos + len);
}
}
}
preLens.swap(lens);
}
return false; }
};
