【动态规划】 【字典树】C++算法：472 连接词

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);
  }
}

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;
  }
};

return false;
 }