I'm posting my code for a LeetCode problem. If you'd like to review, please do so. Thank you for your time!
Problem
Two strings X and Y are similar if we can swap two letters (in different positions) of X, so that it equals Y. Also two strings X and Y are similar if they are equal.
For example, "tars" and "rats" are similar (swapping at positions 0 and 2), and "rats" and "arts" are similar, but "star" is not similar to "tars", "rats", or "arts".
Together, these form two connected groups by similarity: {"tars", "rats", "arts"} and {"star"}. Notice that "tars" and "arts" are in the same group even though they are not similar. Formally, each group is such that a word is in the group if and only if it is similar to at least one other word in the group.
We are given a list A of strings. Every string in A is an anagram of every other string in A. How many groups are there?
Example 1:
- Input:
A = ["tars","rats","arts","star"]- Output: 2
Constraints:
- \$1 <= A.length <= 2000\$
- \$1 <= A[i].length <= 1000\$
- \$A.length * A[i].length <= 20000\$
- All words in A consist of lowercase letters only.
- All words in A have the same length and are anagrams of each other.
- The judging time limit has been increased for this question.
Inputs
["tars","rats","arts","star"]
["vklldovi","lvdiklov","dlkvoilv","likolvvd","ldlvviko","kvdivlol","vlidklov","iovlkdvl","kvlvdiol","dvkillov","dvoklliv","kilvvold","ldliovvk","vldokvil","loikvvdl","illvodvk","vovlkidl","iklvlodv","vdvlkilo","llvkivdo","vklvdilo","oivkvldl","odlvikvl","vlokivld","vvkloild","vlkdlovi","klolvdiv","viovklld","klivdlov","odvlkliv","loidlkvv","llvodkvi","klvlivod","iokvlldv","oidkvlvl","llodkvvi","vldolivk","lvolvdki","ldoklvvi","lvokvild","lvilkdvo","vdovklil","ivkldvol","dikvvoll","ikovvdll","kvdliolv","odkllivv","lvvldkoi","dkilovvl","viodkllv","ldkvovli","illokvvd","dlvkliov","klivoldv","lvlvkido","kvlviodl","klvlvdio","ovlldivk","lkdviovl","dilkvlvo","lovlkvdi","ovkdlivl","olkilvvd","okvlivld","lidvvlok","iokvldlv","vlolvdik","ivlvdklo","lvvlkodi","kovdilvl","lilvvodk","ldvolkiv","vlkidolv","vidkllov","dlvoilvk","vklidolv","kdolivvl","ldivvlko","vvdlliok","vlviokld","dlvvloki","vlivkdol","vlildvko","kllivovd","dlilovkv","lvdilkvo","ildvlokv","odvllivk","odlvkilv","ldvkvoil","dvillkov","illkovvd","llodvikv","ivkollvd","kvildvlo","loldikvv","dvolivlk","ovilvlkd","dolilvvk","llovkvid","ildvkovl","idlvvlok","llvoikdv","dvlilkvo","lkdlivvo","vlovdikl","kiollvdv","lkildvvo","lvkovlid","dkoillvv","liolvvkd","vklvloid","ivlvokld","ldvloivk","klldvovi","dviolvkl","ikollvvd","lvlkodiv","kvdvilol","lolkidvv","llkdvoiv","ldvkvlio","dlvolvik","dlolivkv","vodlvlik","okvvdlli","lklviovd","vovdllki","dovlklvi","lvkioldv","vidvllok","vviklodl","klvliovd","olkvlidv","ovdlvlik","vkldvilo","kovdivll","lklidovv","ikdovlvl","kvvlldio","llvoidkv","dvviollk","dvolvikl","ilvdlkvo","diklvvol","lvkldvio","kidolvlv","volivldk","llkdoivv","idovlvlk","kvlliodv","vlkodlvi","dklliovv","odliklvv","dlioklvv","ldvlikvo","dvloivlk","kvdvillo","ikvovdll","kodlivlv","llkviodv","odlvivlk","vdlkolvi","ldkvvlio","liovdvlk","olkvdvli","lviovdkl","lldivovk","iklldvov","ildvvlko","odkvivll","llodikvv","dovllkvi","odlvlvik","lvvodlki","okvidllv","dovilklv","vodlivlk","klvidovl","vildvolk","ldvvkilo","lvlokvid","vokilvld","dolvkilv","vvolkdil","vlvlkodi","vkvodlli","lvdoklvi","llkodviv","vdkllvio","dloklvvi","ldvvkoli","liovvkld","kidvovll","ldokilvv","lvdolvki","lloidkvv","ldloikvv","ikovvlld","dvoillvk","klvvilod","lkilvvdo","lvvlidko","livkldvo","dlolvvki","viklodvl","vdollkiv","vdolkvil","lvlvoikd","lviovkdl","ldlikvvo","kildovvl","idlklvvo","volidklv","okdlilvv","kvoldilv","voillvkd","vldiolvk","ovdvllki","kdvvoill","illvovkd","dokillvv","ovikvldl","vvollidk","lovilkdv","vklvldio","lvkvodil","llvvdkoi","vlvdolki","vkvoldli","llovvidk","villkdov","kdilvlov","dvlokivl","llvidvko","vlvokidl","klvdvoli","llkvdoiv","divlklvo","vldlkvio","vldlokvi","ilvkdolv","vlkivold","kvvdliol","lildvovk","olvlidkv","vvdiollk","lvlivodk","vliodvkl","lkolivvd","ldvkivol","lvoilvkd","vdvlokli","lvivdkol","oivlvkdl","vlkdovil","vvklliod","dvolvkli","ilkvdvol","volilkdv","lvvkldoi","ikllodvv","oildvlvk","vkilvold","kvivdllo","dlklviov","ildkolvv","ioldlvvk","vvikdoll","vloilkdv","klvlviod","dvlokvli","kvidolvl","kvliovld","ldlvkiov","olivlvdk","ivdkovll","oldlkvvi","dlilvvok","ovvkdlil","ovllvdki","lvlkoidv","vvkoildl","dklvvloi","okvldvli","lkvivold","kodlvvil","dvlvolki","vilkvold","kvivodll","dvlklivo","lolivvkd","idlvklov","llvdviko","vdoillvk","ldvilvko","oldlvkvi","dlkvvlio","vlkoilvd","ovldklvi","dlkiovvl","llvviodk","lvvikldo","dvklivlo","ilokvdvl","ildklovv","dilvvolk","olklivvd","vlvkidlo","olvlikdv","ovikllvd","dkvoivll","lvdlkiov","ilvkvdol","ollikvvd","diokllvv","vvkoilld","ivdlvlko","lvikldvo","villkodv","vvdlkiol","likvlovd","odvvilkl","kolidlvv","ivkdvllo","lildvkvo","kidvlolv","kodilvvl","odvklliv","dklovivl","dvoilkvl","liodvklv","okvilvdl","vklovild","lkoldvvi","ovilvldk","lloikvdv","ldvlivko","vildlkvo","vikldlvo","lvikvodl","vivolldk","lidovlkv","kldovvil","vikvodll","vlilovkd","lidlvvko","kiovdvll","vollvdik","ikllvodv","ivldoklv","ldvivkol","ldvvkoil","livdvolk","odvvlkli","koldvliv","kvvoildl","vdliklov","vdoikvll","odlvvikl","vilvdlok","lvlkidov","vliodvlk","llovvikd","oldivkvl","llvdikvo","vdllivko","lvolivdk","odkvlilv","dlkvliov","kvlovldi","lvoidlkv","olvvkidl","lvkoidlv","ovkdilvl","ovivlkld","iollvdkv","lildkvvo","lvdvkiol","ldiovlkv","kdiolvlv","dolvkvli","iodlvvkl","vvolildk","volvlidk","dvlkliov","ilvkdvlo","lklvvido","idlkvovl","idllvokv","lodvvlki","dvkvioll","ivlovkdl","vvodklil","kilvldvo","odilkvvl","ikdlovvl","vdkvilol","vvlliodk","kdlovvil","ldivkvol","idvlklvo","lvolvikd","vkdoivll","vvdkolil","ivdlklvo","lvidklov","vlovkild","kvdlolvi","kvovldil","likvdolv","ovlidlvk","lviovldk","lvlkvido","ikvdllov","llovdikv","ovdvlikl","vvlklido","vlkodvil","lkdvvloi","vlklvdio","odlvilvk","ldkvliov","llkivovd","ivkvlold","lidklvov","idlkvvol","klivovld","kvloilvd","llovkidv","llivvkod","oivllkdv","odkllviv","ovldlivk","ivdoklvl","volivkdl","ivllvkdo","klovvild","diovlvlk","vkliovld","ivodklvl","olkvdilv","olvklivd","vvlilokd","ldvkivlo","livvdklo","kovvlild","vdlklivo","vldlkovi","dolvlivk","vklvdoli","iklvvdlo","lodilkvv","voiklvld","lildvvko","lviodvlk","vlilvdko","vkioldvl","odivlklv","kildvovl","kvvlildo","odlvklvi","dvllovik","lvklidvo","lvoldvik","lkvovlid","vklovlid","vlokidvl","llokdvvi","olvvlkid","odikllvv","lvvliodk","olivlvkd","kviodlvl","lvldvoik","kviodvll","kilvodvl","vkivlold","kldiovvl","lvklodiv","kliovvdl","dlliovkv","odvilvkl","lvldviko","dokilvvl","lvliovkd","ivklodlv","vlkoivld","vdkloivl","doilvvkl","oidllvvk","oidvllkv","dollikvv","kvillovd","odvlivkl","olkvdivl","voilldvk","lldokvvi","lvvikold","ivvloldk","ovdivlkl","idvvlokl","kvioldvl","vvkidlol","lvdkovli","oillvvkd","lodvlvki","vodllkvi","dvovlkil","kliovvld","dvlvloik","vklodilv","vlolidkv","vlidklvo","ivvodlkl","okivdllv","lodklvvi","kviolvdl","ovkivldl","ldkvlvoi","kdlvlvoi","ikovvldl","vvldloki","vlkvolid","ikvvoldl","divkllov","villvdko","diovkvll","vvdoilkl","vlidvlko","vvklldio","lkvidolv","ldivlvko","idkvlolv","odlikvvl","idovklvl","dlklvoiv","dvlloivk","dovvlilk","divkollv","vvikllod","vilvdkol","vvodlikl","vlvdlkio","oklvldvi","lkdivolv","vlldkivo","killodvv","iolvkvdl","ovllivkd","kodvivll","vkvioldl","vklvdiol","vllviodk","ivvldklo","dlvolvki","ldoivvkl","lodvkliv","iolvvldk","ikdllvvo","ilvlvdok","vkilovld","lkolvdvi","ilokvldv","vlkvilod","ovvdlikl","ikldovvl","llkovivd","lvkdilov","lovikdlv","dvlolvki","voldilvk","lolivvdk","okvilvld","vdvollki","dlivolkv","vvdkliol","kvdovlil","odivkllv","vldikvol","kdlolvvi","vkdilovl","livdlovk","olvlivdk","voikllvd","vllokivd","vvdkilol","iklovdlv","vdolvikl","idvvollk","kdovvlil","ovdvlkil","dolklvvi","ldvvlkoi","lvkolvdi","vlkvoidl","vlivokdl","ivlvdlok","ldivlokv","divvollk","dvllkoiv","klvoilvd","ikdovvll","vldvoilk","lkdlvvio","kollvdiv","ldliovkv","lodvvkli","livkodlv","viodvlkl","illdovvk","lviokvld","kdlvlovi","kdoivlvl","iodvvkll","ovlvkdil","okvdilvl","vkodillv","vlvoilkd","vdovlkli","oilklvvd","vioklvdl","klvdlvoi","vkvloldi","okldilvv","lvoivkld","lkvovild","lkldivvo","ovdlvlki","oklvvidl","liokldvv","kldvlivo","vovdlkli","ikdvlolv","ivklldov","ildvlkov","kdivolvl","lvkoivld","lkvvoild","vkdloilv","ivlldkvo","vvodillk","lvklovdi","lovilvkd","lvloikvd","lovlvidk","kivodvll","lvovkidl","lvovlkid","klvvidlo","kldvolvi","vdllkvio","vivkldlo","lvviklod","ldvivlok","iolldvkv","dkiovllv","lidvkvol","olidlvkv","vklvildo","llvidovk","oildlvkv","dovlvlik","ilvdlovk","vdlokliv","okillvvd","voldkvli","vdvkoill","lklovivd","liklvodv","klvlodvi","dlkvovil","vldloivk","dvlioklv","lodviklv","dvlkoivl","lovklidv","dllivovk","vdlvoikl","lovvdkli","dilvolkv","lkldvvio","lkvolvdi","kvoilvdl","dvlkiovl","kllivvdo","ldlvikov","lvikdvol","dllkivvo","llkvoidv","lkvlovdi","koidlvvl","ovdllvki","dklovvil","livkdvlo","dlvilvok","ilvovldk","lkvvolid","ivvldlko","dlvolkvi","kolilvvd","llkovdiv","vkviolld","vdollvki","dvllviok","vlodklvi","ollikvdv","kdvlilvo","dollvkiv","ldkolvvi","kdillovv","lvvklido","vklilvdo","vlioldkv","lioldvvk","vldilovk","dklvlivo","lovkvild","oildlkvv","vllovkdi","vdvkolil","ivdovlkl","vlldikvo","ilvkvdlo","idovlkvl","lvokldvi","lvivkdol","lvvidkol","vlldviko","ovlvikld","oivvllkd","vdlivlko","vdiklvlo","vliolvdk","oklivvld","vovdllik","kolvivld","lkvivlod","llvkiodv","vlkdvilo","vkdolvil","klovdvli","ldklviov","ldlikvov","lvvlkido","vidlkovl","kolivvld","vlolivkd","dvllivok","lolikdvv","lvdvikol","vdvilklo","vilvokdl","oivkllvd","lkivldvo","vvldkiol","loidlvvk","vlkildov","lkivldov","dloivlkv","lvkovldi","divkllvo","vllvokid","lvidovkl","kvllodiv","vdvolkil","vokdvill","iovvkldl","oilvldkv","lvvodkil","lkvdiolv","lkvlviod","kdlolviv","vllikvod","kdlovvli","voilkdvl","kvdovlli","volvidlk","vlidlvok","llvdkivo","okidvlvl","lvloivkd","vlovlidk","iovdlklv","koldivlv","lvdklivo","kvvloild","lidkvvlo","likvvldo","vovdklli","okdvlvli","odklivlv","ivlvokdl","vivkllod","vlvoikdl","livlodkv","kvdvolli","vkdvlloi","dovkvlil","lkdlvivo","klvivldo","dvivolkl","kdolvilv","vvolkidl","kvdvloil","lodvkvli","dlkviolv","vkvoidll","vokilldv","lkivodvl","liokvvld","lvlkdivo","vdllikvo","kldilvvo","vlviklod","ldvkolvi","lkvildvo","odllivkv","ldkiovlv","idvklvlo","kvlvldio","lkodlvvi","lvkdvoil","ldokvlvi","ldlkvvio","kdlvoliv","lvivlokd","llvvdoik","likvdvlo","ildvovlk","oivkvdll","dlolvvik","iolkvdlv","ovklvdil","lvdovkil","lolvidvk","ilvdlvko","dlkvviol","diklvlov","kvdlvloi","olkdvvil","kildvlov","vlivldko","kdilvvlo","lvivoldk","vvkilold","kldovvli","idklvolv","ldlivovk","lilkvdov","vdllikov","ivlokvld","lvkdlvoi","ivdokvll","ldvkilov","dlvlkoiv","kiovlvld","dvlolvik","kiolvvld","klviodvl","okilldvv","kdovlliv","lvokivld","kldlviov","kvlvoldi","lvvkdilo","ldlovikv","vllvoikd","vlkidlvo","ildklvov","lvdlvoik","oivdvkll","ldikvlov","vlkdvoli","dilklvvo","oklvvdil","lviovlkd","ilklvodv","ikldlvvo","divlvklo","lovvlikd","dovvllki","ovldkivl","vodivlkl","killovvd","ivlvkdlo","ldokvivl","vikodvll","dvlvkoli","ilvolkvd","llkodvvi","kvllovid","vkdivoll","idolvklv","ilokdlvv","oidllvkv","idllkvov","ldovkivl","vollkdvi","vlldkovi","illvkvdo","lilvvdok","lolvvkdi","vlvolikd","vklivldo","ildvkolv","dlvovlik","vidvkllo","ldovlvik","dvlikolv","viodklvl","oivvldkl","kilolvvd","iovvlldk","kvlodilv","livodlvk","voillvdk","ilvdvokl","lidvvlko","ivoldklv","dillvokv","kvilvodl","odlilvkv","ivoldlvk","kilovldv","kodvllvi","kvlliovd","kodvlvil","vllvdiko","iovkllvd","loklvvdi","dvkovlli","dvvillok","doilvlvk","ilvldvko","lkvliovd","ovdllkiv","vdoklliv","kildovlv","livlvkod","kldviolv","llokvdvi","vlkiovdl","lvkiodlv","dlviovlk","vldilvok","dvllokvi","ilvodlvk","dlvlikvo","lvdkilvo","kvdllovi","kivlvdlo","kllvodiv","idllovkv","kvliodlv","ovlkivld","dlvovlki","oilvkvdl","lokvivdl","ovlkivdl","dvlkloiv","llviovkd","vkolvdil","ovkvllid","vlivdolk","lidkvlov","ovkidlvl","vdokvill","olvvlikd","dvlviokl","dvolkvli","ovidlklv","dlvovkil","lodlikvv","ovkvidll","dkivvlol","dolvlvik","llkoidvv","lvkilovd","vvildolk","lidvlovk","vkvdillo","kovlivld","vvliodkl","klvovild","dllkovvi","vvkldiol","idllvvok","iklovvld","vilovdkl","ldolvivk","vvllikdo","ovldlvik","lokdvvli","dvvollki","iovlvdkl","lvklvdoi","idvvklol","lovdklvi","dvlovlik","lvdokivl","divlklov","lilkovvd","llkivvdo","vkivdlol","kodvillv","livkodvl","ollvvkdi","ilovldvk","lvldvoki","kllvvdio","klldvoiv","lvlodkvi","lvidolkv","ilkodlvv","olkidvlv","lkdvvoil","vdlvlkio","idvkllvo","kvdovill","vllkodvi","dilovlvk","ilvlkdvo","ovvllkid","kilvdolv","kvdilvol","vkvloidl","ovkildlv","volkvlid","olikdvlv","dlvklovi","llidvkov","livlvokd","idovvkll","dvlilvko","vviokldl","lkviolvd","ovdklilv","ivvkldlo","vdlliokv","ovldkilv","lilkvvdo","vvikdlol","vvlkldoi","oviklvld","diolkvlv","divlkvlo","llivvdok","lvldkvio","lvdolivk","lvioldkv","vvodklli","lovikdvl","odvklivl","vkvolldi","oilkvvdl","dilkvvlo","llkiodvv","lokldvvi","lklvdovi","klvdlvio","lilvkdov","vvodlkil","lvilokdv","lvkdliov","lovlivkd","dlvkviol","kvlioldv","llkiovvd","okdivvll","kdlovliv","oiklvvdl","ldvlkvoi","oivvkldl","ldkvoivl","lliovdvk","vkodlvil","dlvlivko","idvlvlko","lidlvvok","ilvvdkol","kilodvlv","lvdlikvo","vdilkvlo","kvloldiv","divllkvo","ldklvovi","odvikvll","ldlvkvio","vlivkdlo","vklvidlo","klivvldo","loilvkdv","ovivdllk","odivllkv","lvokvidl","kvllvdio","ovldlkvi","oikdvvll","vvoldilk","dklovilv","ivllodkv","vlvliodk","lkldviov","vollkdiv","ovildlvk","vilkvodl","vovilkld","oldvvkli","vvdlkilo","okvidlvl","ldokvilv","ollvkdiv","vllidkvo","livkdlvo","ovklldiv","vldvliok","vivllkod","vllkoidv","kdoillvv","dvklilvo","dklvlovi","lidklvvo","vkdolvli","lviklodv","dlolvivk","klilodvv","klivvlod","vkvdllio","lvkidovl","vvdolkil","ldokvvil","ldivvolk","ldiklovv","ovildvlk","llvvokdi","vlliodkv","voldlivk","ildvvkol","odkvlliv","ilvvkdlo","klvvoild","dlolvkiv","vidlolkv","lodivvkl","vdovikll","loldvivk","lvvkodil","ivdlvolk","llvkivod","oldkvivl","vokivdll","lkovidvl","kdvvloli","lkodvlvi","ikvlvlod","lvdkivol","vllkoivd","kvlvdoli","kdolvvil","vlodilvk","ldlvviok","vkldvoli","odlikvlv","iklvvlod","dvviklol","kdovvill","dklvivol","llvkdvio","vloilvdk","vdoilklv","ikvldlov","lkvloidv","lldvvkoi","ilvkodlv","vokvldli","liolkvdv","kovildvl","oikvlldv","ilvvolkd","vokvlldi","llvivdok","ivvklold","olvdlivk","llvikdvo","vlivdokl","llkvvdoi","kvvdolli","iodkvvll","idklvvlo","voidkllv","ilvdvlko","vlikdvol","odllvvik","lilovvdk","vviokdll","ilkvlvdo","kloilvvd","voiklvdl","dlkovvli","vvklildo","kdivvllo","vdlkloiv","vvllodik","vilkldvo","villdkvo","lokivdlv","lkidvolv","lvdkvloi","kvldvoil","vkvoildl","oikvlvld","kdivlovl","ikdllvov","lkidvvlo","lvdlviok","lioklvvd","llodvkiv","olvkivld","odvlilkv","lvikoldv","vdlilovk","ivldkolv","vldlovki","kvvilodl","lvkdoivl","iodvlklv","lidvlvko","kdvliolv","okvvlild","ldkvvloi","ilokldvv","vlvloikd","violdklv","lvlvkoid","dvkiollv","ldkvovil","olvvdikl","vollivkd","dlklvovi","ovikvdll","lodlkvvi","vidokvll","lilvkdvo","lvdvkoil","olvkdilv","vkliovdl","vldivolk","vlidolkv","volkdvli","ilvodlkv","lldviovk","vdklovil","vdlkvloi","lodlkivv","kdvovlil","klviolvd","ovdkillv","dlvlovik","llodivvk","dovvilkl","lvkiolvd","ivdvlolk","odivvkll","vlovdkli","ivdklvol","livodlkv","vidlkvol","vodlvikl","koidvlvl","ovdlkivl","dvvklilo","klvldovi","vloldvik","ilvolvdk","volkdlvi","vloldkvi","vvldkloi","lvkovild","lvlovkid","llvvdoki","lkvidvol","vildklvo","idlvlkov","volvdkli","kvlolidv","dokivlvl","lvdkiovl","kivlolvd","okivldlv","vidlvolk","olvkvdli","lvkvilod","dilvlvko","vodvlkli","vkvdlilo","lvdlovki","ovdklliv","ldvvkloi","vkovidll","illvdvko","lkdvvoli","lldkivvo","lkdlviov","vodilklv","vdklilvo","ldvikvol","liokvlvd","ivllvdko","dlvikolv","lvlkiovd","lovdiklv","kvdllvio","lvioklvd","ilvvdolk","dkvvlilo","lkvivdol","iklvvdol","ildvovkl","klvolidv","vvdolilk","kvdlvoil","kolvidvl","vkdoilvl","vdikolvl","ldioklvv","ovvlldki","vlkiodlv","okllivvd","lvikvldo","ovikldlv","lvdkvlio","lvdkivlo","kliovlvd","illkodvv","llvoidvk","loklivdv","okdllviv","dvlvoikl","llokidvv","lvldvkoi","kdvolvli","ldolvvki","vkiolvdl","klvdolvi","livklvod","olvvidkl","ovidvlkl","vldkolvi","lovvkldi","vokdilvl","likdvlvo","ovlvilkd","lkoildvv","vllovkid","kidovlvl","vvlkldio","ildvokvl","vvkdloli","lvoidvkl","vokvidll","vkdvilol","lkvdvoli","dkillvvo","kdvillvo","ivdklvlo","dlkvilov","vodvklli","vkvilold","ldvvloki","likdlovv","likvdvol","vldilvko","llvovdki","llvvikdo","dvolvkil","dikolvvl","ovkldivl","iovllvkd","vlikolvd","vvdollik","lokivvdl","odivklvl","ldvolivk","lvvidlok","lkovldvi","kvllvdoi","vdvolkli","llkovvid","vloivdkl","vlvkoidl","ldvvolik","idokvlvl","iovlklvd","vlkvidlo","ivvdokll","lklvidov","llvidokv","ovidllvk","olikldvv","viovdllk","vvldoilk","dllivkvo","lkovvidl","dlivkolv","lodlvivk","lildvvok","idvkvoll","ilvlovdk","oikvlvdl","vdllviko","vllkivdo","kvloivdl","lvlovidk","vkvldoil","lvkovdli","vlloivkd","vdllovik","dovvikll","iodlkvvl","kvvilold","lvlovikd","vivkldol","vlivolkd","oikvdvll","kvoidllv","klolvdvi","ldkvilvo","ildvlvko","ollvivkd","iokvvdll","lilvdovk","vviolkld","olkivvdl","dlvlviok","ovllikvd","vlolivdk","lvlkvdio","kllodvvi","loldvikv","vkvdliol","kivldvlo","vkvlildo","klldvvio","dvoilvlk","kodlivvl","lvdvkilo","vlkvliod","lvovkdil","lokdvilv","vlidkvlo","ovklidlv","vvklodil","vvilklod","kdvoilvl","lilovvkd","vdkvlloi","dolkvlvi","vollvikd","ivvldokl","kivlodvl","okllvivd","ldovlvki","iklldovv","dovivllk","vlivlokd","odklvliv","kdvlovli","ikvldlvo","illvvkdo","idvlolkv","lvvidolk","vvkldilo","ovivdkll","iklolvdv","idokllvv","vvdilolk","lkvodvli","kivlovld","liovlvkd","vvioldkl","diovvlkl","ldlkvvoi","vidllvok","vkdllovi","kiodllvv","vlvlkdoi","ovllvdik","vdklvilo","lklivdvo","kdovlilv","lvldkovi","lviolvkd","llvvkodi","kovvdlli","ilvlodvk","ivlkovld","kvldlovi","vdklvlio","olkvilvd","voklidvl","dollkviv","voikdlvl","dllkvovi","voilldkv","ilvokvld","oviklvdl","vdvoklil","kdiovlvl","vdkoivll","iloklvvd","lliodvvk","kvoilvld","dlklvvoi","oivlkldv","kovdlliv","vdlvokil","ivllokdv","oklvilvd","lovvldik","illvkvod","doviklvl","lvokdliv","kivvldlo","lkvivldo","dillvovk","dllkoivv","klivlvdo","dkvliolv","kvllvoid","oklidvlv","kdivllvo","dvlvloki","ldlivokv","dvkllvio","iovldlkv","koivldlv","vldlkoiv","ovlidklv","lokdivlv","olvvikdl","oklvildv","vkdvloli","iklvodvl","kidvlvlo","vliokldv","vdokllvi","okilvvdl","oikvvdll","llkovvdi","okvildvl","lvilvkdo","dlkvvoil","vodikvll","lvlvdkoi","vkdlvlio","lkldvoiv","lodlvvki","dovkllvi","vkvldiol","kivlvodl","dvlkoilv","lvkodlvi","dlklvivo","oilvvldk","vklvodil","lkldvovi","dvliokvl","loilkvdv","kdvloivl","illovdkv","dkliolvv","vlldokvi","kolvvlid","kllvdvoi","vikvldol","ovidlvlk","lvvoidkl","klivldvo","odlvkivl","iloldkvv","lolkvvid","lklvidvo","divvkllo","oilvdlvk","vdvliokl","kovivldl","lvviodlk","lvkdvloi","olidkvlv","vidvolkl","ilvdokvl","lvldkoiv","vlkvildo","kvvodlil","vliokdlv","lvdvlkio","kdvilolv","ikvodvll","llkivdov","vkldivol","vlkvlido","ldlvkvoi","kvodlvli","kvilldov","vlioklvd","dvllvoik","klidvlvo","koldvvil","odkvillv","liovlkvd","vdkilovl","ldikvvol","lvivkldo","ivkovdll","livlkovd","klovvdil","kilolvdv","ldkvolvi","lvkodliv","olvlikvd","vlvolkdi","vlkoivdl","lvdlvkoi","vodklvli","illkvvod","idoklvvl","lodvkilv","dvlvkoil","ovdillkv","ilkvodvl","dovvlkli","lovdvlki","illvdvok","llkidvvo","kovdvill","lildovkv","ivlovlkd","ivolvlkd","viovdkll","lvdkilov","vlliovdk","vdvolikl","lvviolkd","lilkdovv","lvolkdiv","ikdlvovl","kvvolild","kvliovdl","lvlodvik","diovlvkl","oilvlvkd","lodkvvil","dvollvik","odkillvv","ldklvoiv","ivklvdlo","dovklivl","vldoilvk","livokldv","ldkvlovi","llikovvd","kvlloidv","vilklvod","ldviolkv","klvidlvo","kovdlivl","ovdllikv","illovkdv","odvvllki","ilvvokdl","lvlivdko","idvllovk","vollvidk","iovvkdll","lilvovkd","dollvvik","vdkvoill","lvkidvlo","lvdvilok","vdovkill","vvolilkd","ldlivkvo","vdlviklo","ldoilvvk","klvviold","odlvvkil","vlolkivd","lovkilvd","volildkv","dvollivk","lvkloivd","llovdvik","kldvilvo","ivloklvd","ldkvviol","okdvlilv","villdvko","lidlvkov","vkdilvol","ovillkdv","ikvolvdl","vlokdvli","likvdlvo","dlvolivk","kvlvodli","kdvolivl","lkiovvdl","loilvvdk","ovlvkild","dlkvoivl","ldovvlki","vviloldk","dvlklvio","kidlvlov","idlvkovl","ilvdklov","dvvlkiol","vdvilkol","vlviolkd","vlidvolk","dklvviol","lvikdlov","okvlvldi","kivllvod","vldvoikl","kvovlild","ovvdikll","kdivvlol","dlkiovlv","lviodvkl","vvdklilo","lviokdvl","kdlvoilv","dolvvkli","kdvloilv","lkdolvvi","kdovilvl","dioklvvl","ldvovlki","dlvkvlio","dvoivlkl","dvvolilk","ldlivkov","vlkidlov","lilkovdv","vdvliklo","ilvklovd","lvokidlv","dilvvlko","ivllvodk","dilvovlk","koilvldv","kvdolvli","kldvviol","ildkvlov","ovlidkvl","vlvokild"]
Outputs
2
7
Code
#include <cstdint>
#include <string>
#include <vector>
#include <algorithm>
class DisjointSet {
std::vector<std::uint_fast16_t> root;
std::uint_fast16_t size;
public:
DisjointSet(const std::uint_fast16_t n) {
makeSetDs(n);
}
void makeSetDs(const std::uint_fast16_t n) {
root.resize(n);
std::iota(std::begin(root), std::end(root), 0);
size = n;
}
std::uint_fast16_t findDs(const std::uint_fast16_t x) {
if (x != root[x]) {
root[x] = findDs(root[x]);
}
return root[x];
}
void unionDs(const std::uint_fast16_t x, const std::uint_fast16_t y) {
std::uint_fast16_t x_root = findDs(x);
std::uint_fast16_t y_root = findDs(y);
if (x_root != y_root) {
root[x_root] = y_root;
size--;
}
}
std::uint_fast16_t sizeDs() {
return size;
}
};
struct Solution {
int numSimilarGroups(const std::vector<std::string>& A) {
const std::uint_fast16_t size = std::size(A);
DisjointSet union_find(size);
for (std::uint_fast16_t i = 0; i < size; ++i) {
for (std::uint_fast16_t j = i + 1; j < size; ++j) {
if (areSimilar(A[i], A[j])) {
union_find.unionDs(i, j);
}
}
}
return union_find.sizeDs();
}
private:
static bool areSimilar(const std::string& a, const std::string& b) {
std::uint_fast16_t n = 0;
for (std::uint_fast16_t i = 0; i < std::size(a); ++i) {
if (a[i] != b[i] && ++n > 2) {
return false;
}
}
return true;
}
};
