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;是因为至少要拼接两次。
时间复杂度: O (sum(words[i].length) × \times × max(words[i].length))
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;
}
};
