336 Palindrome Pairs
336. Palindrome Pairs
문제
Given a list of unique words, return all the pairs of the distinct indices (i, j) in the given list,
so that the concatenation of the two wordswords[i] + words[j]is a palindrome.
- 고유한 단어들의 목록
words[i] + words[j]를 연결시키면 팰린드롬이 되는, 모든 구별되는 인덱스(i, j)반환
조건
- 1 <= words.length <= 5000: 단어 수는 최대 5000개
- 0 <= words[i].length <= 300: 개별 단어의 최대 길이는 300자
words[i]consists of lower-case English letters.
예제
Input: words = ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are ["dcbaabcd","abcddcba","slls","llssssll"]
Input: words = ["bat","tab","cat"]
Output: [[0,1],[1,0]]
Explanation: The palindromes are ["battab","tabbat"]
Input: words = ["a",""]
Output: [[0,1],[1,0]]
해결
1st
1 생각
- 가능한 모든 경우의 수로 두 문자열을 붙여본다
- 붙인 문자열이 palindrome인지 확인한다
- 이것도 brute force 같은데, 일단 해보자
1 코드
- 팰린드롬인지 여부는 좌/우 문자열을 비교하는 것으로 체크
def is_palindrome(self, word: str) -> bool:
mid = len(word) // 2
return word[:mid] == word[:-mid - 1:-1] # 역순일 경우 -1부터 시작하므로, -mid에 1을 더 빼준다
def palindromePairs(self, words: List[str]) -> List[List[int]]:
words_len = len(words)
if words_len == 1:
return []
if words_len == 2 and "" in words:
return [[0, 1], [1, 0]]
ans = []
loop_cnt = 0
for i, prefix in enumerate(words):
for j, suffix in enumerate(words):
loop_cnt += 1
if i != j and self.is_palindrome(prefix + suffix):
ans.append([i, j])
print('palindromePairs loop_cnt:', loop_cnt)
return ans
1 결과: 실패
- Time Limit Exceeded
case_time_limit1 = ["e","idjjjjjddbjhacabheib","ib","ahiifdighccgfceg","eb","hhijchh","gbbgcjbbddjhide","ffbgaedjdg","ehdfhjeibbacfiehhagg","hgcgegghafjcgad","bd","d","ch","eiahiijabh","iicdgeggjegdjfebbhid","abgiaecgdaccb","da","haeicc","hbhcajccfbbe","iicfchfb","hehgiaghifhei","jdbghbichga","eig","bgichgadcfa","ebeaedfccdhch","ddecbjd","aaecbbhfa","edfhfcbfjcb","cecdffeff","eijcddgcdiibjfd","iceid","fecihbjdcehcddbfad","cfdbaf","hdhfbebcagaafhhif","dgf","acahcbjbeddcgbgeefjh","b","bhgjaejeca","gheehhjei","faacbfbfddegjj","dbibgjjgdcghdfdaa","gda","dgcce","gfdcgeedaa","daidhebchfghiagffji","hc","gjjdggggbgb","gdjffhbecbeaf","abjcfcjeichbggciaihg","f","gigfbcdhe","gbcaieijdiggchdhdfjg","ejacbbaidadcajdbafe","cfbja","hdciegjce","ddiiiigbeibe","jedh","gbceehifeiffgg","jbiehedcejchfhdgfgj","edff","bia","gd","gfbfdegaadeefhbcab","fe","bgb","heiccedacfgacee","bfb","jiaaegejed","fbcihfggb","aacfged","iadibhch","acebihhahibd","dgdjgiegcbb","bc","beijebgfae","hefddfijhbfeef","cegfiaeejbgaahjgcibe","dgbdiihciebjaegjc","ghjcggadehjae","cbagggh","ef","ejfd","jifhdcghjfcgiaa","fbjaegcdfbfeab","eejebhbheecfffjg","g","a","ijciaafadc","fjdfbec","jdg","bahecj","cbig","haigcfbbab","jbgbahgefgeicahfb","hcjfbgie","jgbgeaaejabeedi","if","bbaadjdfbefcedagegjb","ad","ddjadidbihehahhafih","bhd","gejgijejjfhbibgd","hcffbhdb","bigfggc","dgaddbicgbbeegiddg","cjdhaeabggjcbicgcgi","gaieejhfhbjb","jjeddajgdgeecf","jfdfhfiecfhfffff","jahbgabgdg","c","faccfgdcfefihaghh","hdabhaaag","hgidhiajh","jacgegjeiedjfifhia","fa","daeabdigd","fihgiajce","fibhadefa","edg","cggddhgffdcdagjihe","h","ideijacae","ebea","cdigcbabj","hdhjd","dbffg","bdiibfgeccc","cefjjcgfahfjfbh","ffajfffjcajchcdia","gghe","beccbcbddfbdddbjb","dgbe","bcdjbgbifacfacb","ajcaifchi","abbjiegaagfajgecc","hdhagdfec","cejahdecfaefdaj","cacb","hg","bhgheidafhgibdfai","bhi","dibae","bdeghfgbhhfachj","ibbedcfebaghba","cjhbcjhgjeceagjecb","hjfabegddgbfad","bcecbefjeijibhbgg","ijjbhdiibcaihefi","fbjcahfaa","ajffbhedfagad","fhee","cbjjdgifgajbcafgehde","ecdejdfcf","jbj","hj","idhhbbfjfb","ejibeh","chificgdaehbgfabfg","jd","hbhfddcidjigb","fhfaibbejjhdcj","gih","aaigfch","cfbihedhijgc","agi","igbdiebhhhfeijgbihcf","dhi","gibbchgjhejiaac","afaaf","iieiidjdba","cdghjjgffadi","ahi","fbbfehdjbjigifji","hb","ifceddgcjj","cgjjcacfafc","hfbfjhf","ifajfjdgdecfefff","fbjdijicgabdiac","ddfbhabacaif","jcbjbgfhhcabdfagiafa","jaeiafdhiddajgag","ijfibaeciajggfbbbaa","cjifgjheafffciihgcfc","ffbd","di","bgjdecccgad","fcaadeaifjefeif","daecaehhafhhac","bfbhbhiecgababcg","edhfihjgdbfjacbbjgj","bjha","ihggihedfdbfhdcfif","dhf","jbihgib","ijfffieb","ec","ghhcgg","j","gagaifadeaffdbbjf","eiaj","jaehbdgabecf","ggeeaebfjejhbeiehhhj","giagdcdhbajijj","fejegabdajhdaji","jifchecihbjecjcgfgi","iab","hgdefageahbccc","ajbeighgagicah","eccbehjbjhdhaaah","bdfeeg","jcacaidgjabeifb","ajhifdeijjdjfbehg","gegbachfdeeehic","gjahaceeaaeig","cgbeihhaifchdf","hgeacdficeadebifdad","bcjebcj","jbgdcehefheahcaf","gheadadjchbbiffj","eafcacbecaaiccae","daejcbdgefefbehjeed","gegfcdeabgjabhd","adcjgbdcicfichgbb","fjjcjjbcibebhbjje","jgfaabcbadj","agfcihc","cbcefdjaae","ejfgaha","hcj","gifhicjhejgdaechje","ifbgfed","hbg","iaibcab","bahhbjjhdfcdbd","ccheiadfbgddiabj","dahiibeaf","cdfejidgfbghifjie","gjjfchehajegbaejjge","chgejcjdchjfahfa","eedfibaaebhhjabjdiff","cb","jfehghfhe","bgciggecgd","cjdbdbe","eicfggjdbfif","cdcbiaafijd","jijhgbeidjj","hhjffabia","jhib","jhdgeiajegcgcjf","beejiaidfbeaheaahi","chfiabfiijfjdadie","eabheiebeegbhej","fjafe","caiddhig","abbbbfagiiebbecgcg","eaebfhcgggechbdahh","igjgd","acfijgifgeeajcaahf","ghhddhc","hefccfjbjhffaiaa","jgcdijbjfdbbgf","gjficc","fc","gceeihhffgha","dfefidc","cadgedjagf","hjhegbjdidf","gdgic","ih","iedfgjddcicijijbaaed","bhghhhffcbfgafd","biijbdacfghgdffgiedj","gebhibefaef","affaig","adifbcdijfcjha","efcbjihfhjcbaec","ccedhf","cfacafaf","gbhgafhbjeefc","cdeaahjeadeejjffbdii","behfidaehdefbhadgbjf","dfbcci","hegbffi","ifecacadggfifhgdi","gcbbd","cabhijai","eihaedjeigibcahhgf","hiafhiajffj","gbfgegd","jacdfhbbiafggedaadg","agbdfebffjjgd","haggddiebjhdd","dgcjihghdefe","cdbfdhccc","jfa","gahjfbgahjeabafhgbaj","ifh","fheigjagfagjjjaf","chegghjc","icfeijdf","jddfajbbjfgfhahdfif","dagiid","je","hhhdej","jhg","igfaghbhbafb","ab","eafaccfjbjffdbfchg","hhdjffgbcffc","ddcaihfh","bfgd","fhbbeed","afiaeh","ahedgidhjadj","ejceddcgecbhh","cbfaeicjidhfa","bgfjegdfa","iaj","cjbidbji","ifbgeeeieidfejebdgb","bi","cjhgaacebgidhd","ic","gfj","aadicb","dbgihdehdjehecehcgbb","gbedhggg","eajahfgideab","dedfjdegghiacd","jjhhj","fec","djb","ifgedfgbgjibdh","fbcecbbci","jjeadjefjhigdg","ijjdacgfjfhgcigg","feafbdbbeehhcigjcje","hgdgcgbjhdjgjifdec","dedbfcgd","dbijagaefbbhhfhbjb","acbdjfccbffijda","fgdahibdjcjcjbbgbjfi","ehiaehhdahbhedfc","ibceiebjdffacgcjfj","deeejch","cbgififgbeeaiigjfi","gcggidjfhjgejaeg","bdcggghcfjcg","ciidb","jbjga","dgjdadfdhdfaia","ihffbgaceedcgcjaj","heiaf","ibbejibaaefhb","ahihiaedbjjbdch","dbac","ijheecc","jfbdgfi","dabhhbig","dihchdiadaaii","ecjechcjeijaciib","ibfijcebfcihcab","jgicejdd","bdbejcjahfieacbhjgg","affac","cbgaadfbeaiigd","df","fgjbiaejbjdage","gchaehejifihfgjcb","ceahiedeibcbcb","gchhbfbabcb","fabeccabfbde","ceaibbbchccdfd","hgfbgcagdeefhce","jb","bagjbedbabgcjhghaiga","dgfebaafgigjbgjedege","jebjaifgeebc","bjjecighcgbdcb","icegbgdhdbii","abaafhjefdeca","caeadbjadf","ieggiceabi","fbfhgiadaj","ci","fcai","jaefgjcbhhghcegfhahb","eiahaadjibi","ffcggjggdfdbigg","ibfgaccadjgahgabiibf","ihaabicgcfcbgeecji","ahfcgff","idegaegbjgeacdieb","gacbcjabgeade","afdcijejijcefhd","jeaaaeibjjbfcfhbch","ccficjd","djdgeddhgfghbbdceai","bh","dabj","jfeciggedaiciih","bceeffjjeb","acgiegacceghjejh","gjdcjij","fddjjejha","haccfcieehdjfgeiiefe","ei","jfddhjjagbg","ihabjcge","bghcaaaadiaafjba","gfbcaaghhhgfddibbbie","bda","cijfcde","jhgigcifeajfj","ghfadbdhab","dfjdideddbfedj","ehdijbcfigjjjgg","fffaiidbid","badfijeh","fjifdjd","fhffffbc","gafcfaiadjfegchehebc","ejfgjdejciheedb","egcbaihjcfac","feaghgbeg","fbbfdcbfd","bih","hjidgjgajicifcjgb","ddfgbfcbabce","cid","hje","dbjhfdjjddfhiajhec","bjeghdgi","ddh","ddfje","dfba","iifdffigcbcibfe","agaifigbbecgabebfcj","aiafffcdjgggb","gjdddeebcdgebeggajh","hjefgdaaaafgdc","dghiceegchaefadia","dcgejfhafgiaaghcja","ibjjadicaahdija","aif","aiaagjagjfhdbfjbeccb","hf","feigfeibcacfiehdj","daicgcdieaif","bcdcjdbahcfbcfhdad","hieebbahd","hfj","agbjabebaedcfcchfefe","bibeegeaadaggah","ahbechgdadagdfbdjdeh","bbceieidhcga","jdhighdidbhajc","ibaaiibchbieafg","fieaiaadeedaii","djgbbeceegjiajdgbjff","acfdbj","fiehbjge","gijfdiih","fce","babghdeiieehabbeef","fcdbec","dhhhjeciidb","ciigjcgcjhajhcgggd","ddhb","hcihaghhdiibgdjcdadh","ihigidggfec","dfiaejijfijedcfifjd","ffchhbdgecbijea","ajbdedagcjeicgjegg","igcbj","fijfihbdadedhhhegh","fdhejbjc","hidgjbdejbbgii","igahjj","efcjgidiahfddbif","abiijgj","cjadegejggdadgafid","cjeeeffhgibadhgda","hfcihhhfjbefccehdif","agggjeaajcd","fadcacajgcaa","eieedfghjhebceaeca","hjdijeffgbjbfb","dibefcdfjgghggfj","ii","ghdeef","hicej","jaad","jadjebhbi","hbddeigifcbdehaieg","dhbacdhgjcac","bfbf","cheghajghe","ggegddhjgdgebfiacdee","hficjedfiajjch","deijggha","fbijiacchff","ifbb","hecib","afiibjieehafhhf","fbcghdcehijjbcafg","hhgjefegajjjicefdga","cbcic","jabjagdehdejhcge","aajjgiijbhaabihi","hfheegbigdj","dcbjhigecbgfcieifigi","dagaieccjjghdbij","djeic","dbcffighfeeeecihj","hgbbaiggieajhfachh","jaifiejdccijbeghfg","bejjgae","gigaedicijahhea","ecfihjgieijcaaeej","hbjeejjiiicihabajea","abigifaaaca","gahifhjja","bfchedbedadhdchje","icecgacjhjhab","jjehhfc","jhh","eecbc","dghgcfjgjjfgbbg","gcedfaf","deieadhdhcijhji","hdhgjgjdahijjchj","jbjedhhceha","ah","eiiijiahcagjajad","jg","fifb","dgjfjhebgefdggighad","cahijjecababibfghaf","dgibjejgaajfgbbbd","dccchjijbeaaedaijj","edijaajbibdjcfffcje","fajacdhceecjeadh","iecjj","bfdbe","ighbjiijiag","hhfbdijefcgchchhgij","hjgfbaiifbag","cbghdhgccdecheeejdec","hidcch","eccjfdggadichgcggjca","bedjddhaijgdia","gehigjchhebf","cdbjhggddcgad","hejfbegedabi","iddbdehcdhffcjbib","aacaacijgcffiifaaieg","difchcaeae","dgcgeighihfbd","ijddgddiie","digf","ijhdabggih","bddfieaah","chgfcaehdaiabeb","jaegbjejedfdjgcbhje","cddicdjcgifa","daeeae","bhe","dfccifjfd","dcda","dijffciefbici","bbiifjffdheajgee","feadgeb","aec","gbbjdedhgagabcdiibag","ihdbihidgcdhgcgjjca","fhj","gaaa","bjcfhhhfjchhg","aibhdhbehbjfffbhf","achdgcjdbiefeefg","jcaia","bff","fdhebcbb","iifdahbfidbi","idhfaii","fcejceeif","ffjiabeigcffg","gijjedgcjih","aieegjjehde","acgagghj","gifaafeceggbejg","cg","dhbjhgdfijihbagjed","ddbgbbhfiahhaadcjch","chd","dgegdciahb","jjhgehc","ecchadaigjhjg","agacggb","hhjbfgfdjbbhje","aabfccfaghgibei","effdigce","ebhjc","ajadfdhacfjibggcjgfa","jajefhfahafgbb","dgafdcfdigcdiecba","i","cffddfhjbbdedgighjcb","ijea","jfjfgb","ffgchieehjbhh","gcaf","ihbcebdeacfahga","jicafdedgbi","jdci","bha","jibfhcaecf","baj","cgj","hhfadicafghfbc","jahdhjffefhgfdbb","ed","djebeeicjcfhg","hfieiddbghiajafjb","cdhfchac","hihaccbfeaeebfaifhab","ahejjdgcg","ajedbgcffcidiigcfdh","jaj","fbhjeaidde","bbafdhebeeie","afie","ehifaebfajdhb","efbddhdfc","gfagjdcecajbjgeiijg","deejbjfebj","bghfajedhcfegjgfhi","gbihfdciica","ebiiedjcdhj","jdhdhjbcgdjdhhb","ce","ibdfbdgf","ceejjhd","jeffcciahiadhhhcgaa","faafjjeabfff","jig","gfachiejif","fjffcdjecbgj","cbeb","idjfcgci","jcbgaedhhfiijjbgg","fcgjchfhf","jecacg","ihagifabhahdjef","egiagegeje","idhbidchdbjf","jbbhfide","dgfiegijbbeee","fdcgcddhadjge","acgeedbdgbhcd","jfheaba","cdhiejcefeab","afcecgeegfgabchiaibg","cbfjgddbffhge","bgecfa","hbhbjhcfefgdjdihcb","cbiiajhb","bafhdbhd","hffdbfhbhjcf","geicehibhggfaigbhaea","gfhgifcef","idbadegfef","ejcdia","adijcehcchgcefaei","bgdcbejgcgjj","jeafcaidhjicdgbhag","bad","fdhhcaadig","igcibfdegg","cjajaj","agggd","accg","jdcijb","hgej","igabcheahdhdedcjeg","jecgbae","ihhfjfdhjgeibhggd","fcadaihaadgdbe","daebdbbbfabhdcgedc","adhhieahjj","eihdaajeihjjgefijf","ijifbhjdbbgggheefd","eghfeeiebdcg","dbbjghcae","afhfbahehgbjagebjcgh","diajdhbgh","bjh","jbaihhjcdaejchad","jjibj","jeiggbcbjcgdbfdajhi","gbfhijjiccjcfdd","cdadae","dgbjahjgijieidhccbh","ebicf","bfhjiadhbcab","cehcfecgfafdfbcbefc","deab","ejif","hcdfcbijf","gbaechgfdehccaec","hbbbgdbfjahghdadg","fagejabedjgbcbhigdie","haaeffj","bhieii","hgiajfdifce","iccifcjdhfbcaj","gdceghbcjdejhgefaid","ifjejachbjfabiecaj","ghfiahe","fbcbiid","gcha","jiahjicgjggj","jfiieefgi","dbaghajgdifdiffeihjh","gbfbdacebgeibdhh","hjgahjhfjfeehhjijji","jbfdfdjhdbf","hhgadcecg","iejjfbeiafjgif","jgifdfhhfa","ieiifdgig","gb","hhidcggebbdcb","acajfj","fbehdjaechejeaicieeb","hccejebjfjbeg","hjjdaafhd","bjfga","ijdfb","gfcjbbgccbcdfba","eecefficdgfhdcceee","eh","jhgadfhbgbibhah","hjfjdjgedeecdfghji","jjee","ajccdebhabc","ecajfddhddebdj","gdfecjbgecdddjg","fjdffgfahia","bjhfgg","jidhacdffgjaje","gfjc","bghdgbiabjiig","fhcgdhbfieiibicjggi","ifaghc","jifegfghaagfbcj","ihagdgdigebaeddgjb","gjebd","dgghgj","gjafabbjdfa","bed","gdbabh","jhidgefbb","bijjabici","dfaabdbfejbaegadcgjf","eiccdihbdfej","fheibcic","jgfa","diagbeeeeejijfcb","ibfjaehi","ficifbahdcda","jifigjiacjjjfcdh","jif","gaacdffehg","fd","jibdehabehi","jjgdgccaachbgcbb","djhjgfadcg","ihdfgihjdjceb","ihcfa","hdhjgfjbehf","gdbbce","aeahgcd","igaafcicbaedebg","bg","bacjbahgjjjghgdaec","diead","jcciacigghgdj","gieeaahabbbcbe","ehfdfehfgccdibaj","cdgj","deicdaf","abgdcdcb","ddg","gfbiiicafhicdibdd","eachjihhjf","gdfa","iidgiiddhfigejhggbef","fieeghad","fhbhhdaacahcjejcd","jbeafajgbfj","fechbhdhegcije","jeebhcbefbhagcdjdaf","ihhihiffd","jbjjehi","eegeaf","fadeggjdchdej","acbjehgj","eihbjhcd","iegibahidfgbcc","facedfjjifdbdifjjh","cgbgdibihehghiicihid","adaccaidjddc","ehe","fcjjfbhfejfdheade","figgbccjj","cgddi","gjabjgjcjjggcfacdd","ihabbdajcfjijjij","deedfafihecjhgj","fbjgabegafdibce","dhbecbbfceijf","cjfihbjddi","idihffi","eccfffgecgaifchffjhb","jjf","jbgbcjghdjafaejbhgd","idgahihdbhcjjh","cdiceaihge","hehfhb","gajcjhhd","beaaicdadbiebbaaeih","edibcceiehiabfg","jcdbbbjfhgchb","bdig","hfdic","bcba","chgbe","agbifafiijgehfi","jehgde","fhfjgdeagjgggbffjjcc","fhgcadddcjadba","dhfbgib","fdgjddidjdhj","jgjcbhcdcadaghibb","bdefjhcadhhgif","dffbhjcidhhiajafajff","jf","hjbdbcgja","ihidfjdabediihcbc","jebffhbabadhg","bj","gcifdijaadcheh","gadagbjiide","cccdcgebgdcgdbjicj","aggiefdeaghjeacbjc","iagjgceig","djbbdffaadfihbie","hd","jeacfe","hfbihficfgbgji","afiffeihhhj","jgbdedciahfbjga","gcijafabgdiaefd","efgdigaiddhhhdh","bjiheaiedcjjcde","abdhddfhc","gadj","ihfebgdd","ejhddgc","ahbhabbejjhhhhjdae","gdgbh","idhhb","iehgdhh","fiba","fchfffiheadgfjehe","iijdjdejebhijbeibc","fgbeddfceffegieghdb","cahabhiahfajaiggbche","bjbjceghfabhdiahfd","dhafaegbeciddijdddc","bf","agdajfjeifddfcjfb","jdecbfbfafaf","iahc","bahceeccfbehhbbhbcd","dhchbi","ig","ieahfadceecjj","ifcejedeejdfi","ieabdhibdcbdjiccdcj","acabj","hgaefddcbggbadcjbj","baedfhdjidfbgebce","jbfbgcdgje","eheecbj","jifcfiiajcejid","igggcjfecaidfa","ifeaabcddbiefcaj","ahbggejhcafifhcibed","decgfgbgaddagfjifji","jjghabahifjeeff","jbadeh","gjejicfgcfgicj","edbjfhae","efegfija","ie","bgcaeih","ecaffifhhedgag","cfieeci","fbjggdjbajhhjjhi","hciebffcffbagdibefi","cdfdjfedcfaehihh","aiciheaaje","cdghfbajcheh","diiajfjb","cfbfdjbhbafhc","cbefajdcgbajjaijdjae","bbeeiajeiifjibdgdbi","aigcggjcaiecifebif","ihcag","cgifghcabagjdead","jcichdiibfcbfd","djifaggejhij","ejigbbjg","dbjighbicji","cbicdjifjebha","fdjbagihifgdd","fgfdjbh","ffdecgji","eaaabbadeifdbjihgd","ejciaiefecicegech","jgajfjecddbfjcjjbid","bdjjef","abfaeeah","afjebjjaihebibc"]
2nd
2 생각
- 역시 시간 초과가 발생
- 시간을 줄여야 하는데, 어디서 줄일 수 있을까?
- 바로 눈에 보이는 것은 이중 반복문. O(n^2)이므로, 이 반복을 줄이면 시간이 줄어들 거 같다
- 반복문을 두 번 도는 이유는
abc,cba가 있을 때abccba와cbaabc두 개를 체크하기 위함 - 그렇다면, 한번에
word[i] + word[j]와word[j] + word[i]를 검증하면, 절반으로 줄어들지 않을까?
2 코드
def second(self, words: List[str]) -> List[List[int]]:
words_len = len(words)
if words_len == 1:
return []
if words_len == 2 and "" in words:
return [[0, 1], [1, 0]]
ans = []
# https://stackoverflow.com/a/30357006
# defaultdict는 없는 key로 접근할 경우 KeyError를 발생 시키는 대신, 키를 생성
# checked = collections.defaultdict(False)
checked = collections.defaultdict(lambda: False)
# words가 일반 list인 경우: Runtime: 732 ms
# words가 deque인 경우: Runtime: 516 ms
words = collections.deque(words)
loop_cnt = 0
i = 0
while words:
word = words.popleft()
j = i + 1
for word2 in words:
loop_cnt += 1
if self.is_palindrome(word + word2):
ans.append([i, j])
if self.is_palindrome(word2 + word):
ans.append([j, i])
j += 1
i += 1
print('second loop_cnt:', loop_cnt)
return ans
- 응 안 됨
2 결과: 실패
109 / 134 test cases passed.
Status: Time Limit Exceeded
case_time_limit2 = ["hfjjh","jjhjadccehdaihaa","ghbjehbiiddcbdebj","aahidhgfcea","bijia","jiic","eiffbcjfbcicfid","hfjjffedfh","gjgfiid","cedhcbbhedh","adecahhchchajai","icdifcegdjjga","dbjdigebdagg","ffeifjbgbifcbf","jfahadehgieadidc","hcfjc","ddfgadabgjgcfdaijdgi","djia","bfceggbh","ajdjai","iiecied","g","bfehbhgfgdeecdcbedej","hcefjbagcgijbbgjgife","gaiebdc","gje","fidfaacd","hggacehhi","ageejgcbgid","hj","hag","iiaffaaaehb","jjhaieb","gcacjfaaadj","ggffd","jffi","bahhjfidheaedccfffe","hf","jafjhfdgccggifjija","bjfef","fc","iddghhac","jigghfcjabhcecfg","dfcieabdeeggi","gacaggdhbhfgafifbc","hedhijhe","chcaeib","dd","aiih","jifeacabhfcbajhjijad","jbicbcjajh","cjcejidihcfajadacbjc","d","bfdhedj","jefhhhee","idbbceai","cddfiebjchd","ihahbgebd","bjdcadjabgcfdfdfcgc","icahfjeebjejfbdjgbj","gigfafcccagc","jijfbhigj","dbe","ebagbaed","hhibeffg","ji","aiebbebheaca","hbggbdgjhb","jfhjfhegdcfh","dgjfjhciahbbcdcjhfj","cj","cgdgdibhb","c","jjcjcbcdbgcjjeddj","ghegjabhadgj","fjceibhighbd","ichcgbcdfjaiaf","icgechh","cbfdjihieghfdhjibba","daifafigfagec","ffedch","ef","idbfgddjdgfa","dieiaif","bjb","bfdabe","hhhbagcibjhea","eiddagijgg","cheffaacbebdbccggeg","fgichedjccf","ffijjab","ceee","bhgebijcehdejfd","ae","dgdb","ebahjaijdhj","eafh","hcbgg","i","dggig","fhhdcabagha","gageehc","ebgiabgjeehdgj","fdddhaacgbcj","gg","gaihbciajeiafjdbjac","bcecafibjhdia","icheeejchcehbchca","efj","hdghgdffbdedhbffaf","daj","hefdjhehhfbbgcgid","bdbif","gfahaffhbid","afjebfeceahh","abedaajaifcbhb","b","ddd","chjibehgbcf","agdfaidfdefi","iadcgaeh","hgchidfadicgjhfbac","aibhbcbfjacb","jdeihjghdjehgbadd","chddhhibfigihf","ga","daejabhibeggccggfh","gfdagiaeeaccdedfcgf","aagcdfehjgab","fbgcjbafgjj","cjbcfhfac","ededjagfejiegdfchj","dcffe","hcjihfjeeeibcacbd","dhagfdcb","adegificeaabihjcdc","a","gijgcja","hbihhb","dabhabdghhahh","ffceigijgchg","jgad","had","hicgecgj","bfjcchhaajjh","chdhbdcigedacgeffdi","ddiegiggaajhfhgj","fdihbfebh","ebfgdbgb","agegedabaj","aagdghihedbjd","begjcjijgcbbafjge","dif","edcib","cdgfadjhccbabdj","cc","fjcfdiehhac","bagdbcdf","ejgcahiffe","aje","j","iciffhe","chibehgbdaf","aj","eedggichbejacb","hjid","aiiaba","gjacfjdadjeia","ciibjhiafifjdj","eaihdeccfa","jccbchbei","ahhifgi","gbfafjfcaeihcahhggdf","jffejbbjhfbhhjhac","fa","jfcdfbffhjagceihih","deebdgegi","iaighgeeiehfgfafhg","h","cghe","jjhbfheig","gfgbfbfadiiehceiaih","hedcbajajfd","cjgeeibfaeedgjcibhi","iddcfejbhiibifh","eahabbgijfaf","hh","hfjibfgaffifgccbgf","ihdfaeechgifbedbd","chgfif","ja","dddjdbdddfgcb","aiaaahaaihf","hhhchaaegijebj","fdghbjdcfejdda","fjcgbf","dfaaghehcehiigcbighe","jejaajhajjaagjdcehj","jbagiighe","bcbcbabjac","iaegddagibac","hgaccdcggeigib","jgdcg","dbejdiabec","fhjgbaedf","jgbebjbhcidcdacdhaj","igefbg","eihebfej","f","bihdd","bcid","fbfffggaead","chdjfjjeba","dffdjegdecig","eaafjcdgbaaadjeedhia","degabdgfghabgihfhf","hfadbiaafadjj","ecgchabdhafhegghcfef","ibchci","hghjhhb","baebeehj","beaigbbha","ijebgb","gedf","jcdchfchjia","cgifgaejhhb","aeeiifdfbbfeee","ebdgcbihcgchhd","cghgicciccbih","gbdfabfffbc","fcbgabiadijagijdcdi","gfce","ghechaifhfifjefccj","jfaifgedgddhieebafei","ihej","bbccdeiiad","ibdgega","jgjfifidhihejdiehfgd","dgd","cdgheefihcbegd","aibahgdgaacgddcfhgde","fdehgafga","ebc","ec","aeeacaafiefhgihc","ajbahjcbbagd","bgbhbibgcbij","dbbbggiajhaf","habibjjfg","aigicbjbdgeajg","dac","hbdcfgii","jdhacfefji","fidja","jghah","egbb","aadejc","ddcebfdj","cig","ccacjgbce","jcedjajg","dhae","jfeadgce","af","abhfhcaaab","fbebjdd","bceei","ggadjfaiifd","agibaidbc","dhfjccjebegeb","abfce","jhjacfaabcb","cdcjahg","bejah","efbigehihhchcicg","cegihebijajejggddcdi","bgjjdddiegd","hbfghhfcjcjacegfa","cgicdahfgfeagaji","ghahgejbgiafj","chhfjbdichihjg","ehhbacaahcd","bbhgichfeabaaf","hd","aijacdjedhjeja","jhebaidjb","bjdfjigfghbeccc","gbagidh","dcgdebghfcde","deha","gcjjg","gcgeehghgddbeef","bhbjcfh","bjbhdjgifgea","dg","bgecib","iaegaab","gjabeddabffbbgffjfbi","fjhdcdjhf","gieegfa","hdacifdfefidibfjaj","fiacdbeifjd","aajhfeejibaaegdbcjbc","ejcbg","chihgcdchbhd","ccbaefeajdggdiab","ah","ibhe","dihigjeebcb","haifiidjbiggjgacgg","gcfdffi","jagdfcigdcjhaij","abjjecbgjafeagaief","iahdbedaihda","ihecjjeh","fbjjhgfjeda","feddbhghd","jefjjaajigbdg","ajhcidbbe","jghaaghdedjdae","bgcje","jgafgffebecacddjec","gghfedidhfhfgiddhgh","cjeeafbdfhfhgfhbeg","hfdecejiaice","cafihjeihf","beahdgejdfaccdeidebe","dhjcjegb","gdgegfihchec","icdhacfdfgej","jbcaabagegjjjgjeed","fhdecbdhbfgdfijjh","dcijiadheeebcddhha","fbhba","ighddcjifdgjhf","jbfidgb","fcafbgbbhdiijbehe","eibhgcc","fe","fghihiffhach","defb","ajaahidiecgchgdjai","fhga","gabgbaiiejcfhd","jfbbefaihebdbfee","e","affdgidf","ajijffcicadfaede","cbcijhjdbcaghig","badaecagbcjbehfihiia","ajdffgbbbe","gdidgjggbbcdjagfghc","egfdjcabicicgb","gbgfecihfffdajia","aehhafc","jghbda","ibidgcgdgfijdj","aijeeedfeedijegi","gfjchcbc","fghaefbdbccebehfecj","cifbiijbbhaeagaha","icheghdgbfaffefahg","gfajdhhhihiieb","hdiheccedehddhh","cgieidhegj","bb","eeeihaj","afadcbfbefdeadid","icchddijdfehi","cgicdifbefggae","ac","fhb","cifdfihe","fdcdafb","gj","aicbjfgigbbhafbcj","edaidgeajc","igibcjibbddedhchiegi","idgijefeicbffd","bddh","dfiibcbgeedbf","iifafgfcigghbbifajbh","hccfebgjeiegib","igcfghiejchgjcjdgi","efjijdag","jebjhiagejbh","aahgfdgghehbacjffhhb","fhhdiejhhijj","ccbgefjcjhef","gcecgfa","cdegibfcefggffa","ihcdbcagj","aegdgafddjebjfihc","fjhac","dabjefb","eaficegaehbjihejghjb","cbihhiigddbcbdjcj","gabiii","hebababgahfbghgcbg","ghjadeijhffjdgbfiia","cicgd","figcggdjddadagci","heacbabgg","ciciddcefbjfd","jcbgiaebgi","ecbbhfidfejeafad","fjgb","aja","ijhgbagjifgaba","jheegdbgafggbgacjhhh","aeafhjidejf","bggbbgbaec","gajaecggadghg","cjhhicjb","cjibjhiabajjba","gacjcceeccga","jehghhciaicg","jfej","ejbehjeccgbjhidc","gjgbaacgb","fbfagjjb","bfejaidcbebdieaajdc","bgfadcgcibea","fbjdfegegiehbfjiif","gcffdgeaffjadhbfgf","hiegdeggggdeieebi","afejga","eih","ffhjeggdgajfibghahfi","efihjjdfeedhcb","ggbjafaeccjfeaffiejd","dbfhdjfcfhjgaajbhf","gbgjhggfdeefcdjaahjf","hbgiecefdjcf","aeg","gbeadhaibaef","jfb","jjifbbfedb","aehadehfjgebgebchiac","eedaeaegbjajff","bc","iba","jihjeb","ejj","cggh","chbdjh","ejjf","gfhbhdfhibddebhgbha","idejbhah","bjgehibbagijbdgcg","jbegcjidecchghjb","fbbhidjiicbgjij","hfcdjjbhdh","gjffffddafa","cafijjjbgciefc","agdigcahhbhfefgccfff","hcbcfeifdfddgafgh","icgdjbgia","aeaifhagecacdiadgih","ejcihidifjdibdijb","jfbajg","igfjei","eebacgcdh","ccjcicgfiafhg","hffabiad","gfjdbijhb","dggcfeegdefcgibabb","igigeffdjch","ebccadcejbbdbjd","fagajedfeiibbbaba","facc","fcdddijdecbgf","jcgcijifaga","efaheihgd","iidcidedeeeac","bijaaacibeha","fedcehf","jcdjacdecjhcbajif","ii","bjfbhjhdfifeajbfi","hdacigggjghehfjffd","ejjdbgigfddfjfcfi","fhfdgbhg","fhdijh","gecfj","hbceadacedi","hdegea","bhacieg","gddcehdeb","bagb","babefafbicdhg","ehfcib","dajhjifhihggjcideije","ajgehdf","ehdjgdhfi","dedaeid","afegjibefjhajhc","jhfbjhhabbjbj","deai","iceaadgef","adgfdbhfgebg","ahdhcdgeajaaebc","djbbdgfbcdid","jffgfcijaa","edfdicedaijgbfdjfb","fafbagbggjjigfdhj","ejecjdbaaeda","ibcib","dfh","idcdjcdjhcigdcbidhch","jddfjdghchhbhahajbg","fiej","cfcdicafgagjfddhjig","cdefhjcicdicjheabfhj","hegjgcijhjhef","bddjgbcbbcgiiibahj","cfefdfbdhejch","hifijgifjjgd","bhijhebbcfhfd","djc","dhdg","fhhfhdicabg","aahhhhhhfdij","dbifbjdfde","iheagcgghbcbacch","jhccfghaiahghec","gfhdfahg","dbcjhddiadjbdihia","gihfccghehejdbbigi","cfjgadjfejc","hfjaheaij","eaiediddagbajhdibbeh","afceebehhcdgdgeagcjj","bbaiichig","eeabahbd","cacid","cbjjcbedaceejgfgbdd","fgddhbhccdbg","edieiibe","cjehcfbjgebgeijic","cdihdcbjdcchgiigff","jhdbhgcbhjabejhaac","abejecggcaa","hahaabdfachca","ehccgifccedabebaega","cdijehhdjhj","cffdhbedhhcjdc","hejigcideicacgigfgbh","hef","fehjdbdh","gjeh","aacifhaihcg","iecgbefdiachc","icdhjgei","befi","dfgcfgggd","dbifid","cebcfchhegahdif","gbc","edcbf","afajieajeahhgdj","hejifjhcjga","dabcddjfjiacadci","dii","gbbjegjaaabjeabfac","gib","beeehhdi","iciba","fjj","eagfcggaejgaach","ieecijcjgiejbdgcbjh","ccdbagejgjjj","bjgbieecjec","aiahagc","cihegbhcbjce","ehjahedejjcfdbdce","hiaifgffief","hjijbabh","beefcabjjhfhejfaijec","ihagfgejdfjdagedh","gefhgjiiiheijgjgfjd","ahf","afhdfbbccabagdijb","jiaaeaigbdfgcd","aaeagdfaiggbadbbdje","aacijjcbac","cfcecadih","aiihcbgacigagjai","eigece","eid","jdfccgbbjcgafeahhd","ceedfieafgefhjbeed","abbagibhcedahjee","deighgabjdigfd","fajd","egciijadbhfegdhd","bbbicigegeggajj","ecjegigbcbih","hbdbgghcbhg","babf","dgbbdefbbicedaebc","jbdejbdhiedjdgg","chghddidfabdcj","ifbahdciadfh","dfbibcgfhabcdadffh","bahcigdche","hjagiihgddiecfgb","bicgeegihbeaideaedb","chgfafdhhfdi","icjagciei","hbf","dadh","aafjicafadggjhfag","bjgahdifiddahbgc","cbf","hhgfeji","higjifecgcece","egffdfgjajefad","cihhcibf","aiifefj","fgiaceagd","fhbdjgbagiecaea","fdaje","ejhbfdecdijgbb","hjbicjjea","fjbibdcba","jidheejcicgidgbabggb","aegcjeehbgbhfdjagh","didjcfggcc","hcdbfjgfbfhd","ecbiij","bgebbjiehhbgahbaf","ghhgadjhbch","daggahhbdfg","dcfgfcb","hbaadgegjacf","jdfiajgchggfiiijbfib","jjedifggafdcfebihii","ic","fghd","abcbddhiebcie","baajeihgefbeheaiafb","bhbiggg","edejg","jcecfjcccejgdheaba","habcfehdjgfeh","jdbefaefbcagg","ibcfacefdehhbdcedj","ejiig","dihcbaeb","hfhafdbjeffdaccfh","fgabajabgjgi","hfgg","dfdaeabaijjfgbef","jdifcagfac","gjafcjahjaiagjfab","dcjdficcihfdbfed","ijbhdieji","ejddagihhghbd","aa","efa","fcffbdhdgejg","dhfggiffbfeiicb","gaghca","jiffbcgadeaec","gdfaih","edgbjgcac","jddefebjbgdhifdjheig","bieeccbcg","hfchjdfddgbbfebhehg","cebhdedfibdajc","ijgiiijjabhgehicjfa","jggajcbhd","bebbjeiigfchh","ijfdjfij","gabcdbi","ehcahai","jafieaihhdag","ahiiieijjbc","cggefea","fcigjchd","eihgfeg","aacifaegh","ejahacaddbfggfji","aahjijgecheajiaaa","dghdchaggfefbgie","idc","jbbc","ebbbibbdc","igdebjccidbahjggiai","ibidifhi","ejigdajjidgggijjhbfg","ggda","hajfjea","igihjijj","agjdccciefcg","feadbeeejjgibdegibbf","aideigbjh","diaibidffjajjaccej","adjdagb","beiiebaehhe","ggfgcjddeea","jdadfa","hjfhh","daadc","dhfhhd","dhiaejjeb","bigefgcgacbhebhcfj","gagbbjjfdfghfcddeei","ahfhhibaj","dedgb","aefafddcgdea","gjehjhie","dceai","jbbhbgdceihf","jfdiha","fedf","cgadgibba","jedchjcjggidbdefea","jbgi","di","hjgecgggcdjiecfadag","cajjcabbe","edgjfdjcbficf","ib","bheeigdcaieeedief","bgajcfiagiffbdhd","gicejbhcehaa","hfeahgeghdgi","adff","daiige","djcdejfbjcjc","jdhchdgfehgefjgb","eifihfajfhbebejj","beh","icjcf","debb","edhhbahcggf","gdjjjcbeaehiceicbe","jaabgadebfdicc","db","hegbejeajdhhegh","gdbebjfcebcfijefh","faiddebghgi","ajahfgbjgdjcjb","cbahbhibiffb","cebadha","hffebcbebifjaei","bhejf","jfgichiehff","deiafhja","bhgjbbfebaibhbgcg","efaicjecjaedc","dbfhfehcfbiegg","jehbcg","ggceacgchchfhchd","cjddjgbiddhh","bbcgeidhejjbaafceb","eeaefibabgdbc","bgciaafebhajbbdehf","ebfdbihggbbijhgeahd","ajadbcccifieccae","ffg","feijadcfcgbj","aejigjfbhchjhfbhgfeg","hbbe","efjabhcfibjbcae","hjfbfcahbieejgaaa","ageccfhdgcdfah","jfiieggcaacffecj","igehcdedfdjedhbc","fcebfacibggdeggjeigg","igcdg","ciajeegd","fghejejee","hgbajahhedicf","iaiiibigjhbfjfjjicab","jgacdi","eggdieeij","chae","ahhabhfaccgcehcfdjgc","jbbbfgiddeecgjgbefgf","fiagbejefhgaghbaibhc","ai","jbaiccfddeeafa","fijbhfbhijecbiijhga","dbfbaeefiihifbfbjed","eeefecjah","fdjedeghfjjfb","hciiiie","fch","ifdijicbieg","bib","agcgcfjcdfdiejcjjj","ehfcecjjaeagejdifdh","jgd","jhbbfbaecci","cagjfcifcjaheddc","jcfcghgi","jhddbj","djigjaieadfia","ebjfie","bggbcbbeghebgc","ijh","chaagejfabddcjgbgdd","gjfj","ahijcbcejbhifgdfiaej","aahbidcedh","faeaji","eafhi","babcbfidfgga","caahbefhghbfd","jgccdidchfhffijejac","aacg","ddhfbdfi","adjgefgiahdahiecgge","bgd","hjcjdi","hgdcbgjfbagcjdfg","hbjfi","iefhaefhgbdajjgdhbj","jeehadbbjidjb","hcc","bbfjfgggdbhhhjhbic","dfe","cfcadgaij","gageeddbddaj","jfgfhcgfc","hbgcfiieeed","hebdfefcdjj","baacajfeeg","figffccgecijfcechhb","bgijbabahjjaajic","caheegjdfdhgjf","gjggcaahibgfg","hfi","ififb","iaacbfa","jdegigghddbgjhdb","dicediahba","eddehcefacejda","edcgfhcgeee","cijhfdjfechjae","hhgcagjdbffgjadhe","caeedhjhfibjecggf","dedjbcdiahcbaabgeh","jhie","cciejcbcffeefhaid","hegfedgfceifcebehjc","hgihahdgad","chbfhc","ebdi","ghaacaaef","gafacaehghcifibjgi","cbiddcagc","dhhgjdaic","jaiddajhdidggfcdd","hicifcbhgeeej","fccjgcjjcdf","daafdjdgdiihdjf","biidhihjeajiidggjcg","ffiecghhjacjbec","didcchdibaihbe","hjigfbgejjjhabh","fae","cfgcgjcfjg","idbbe","jejabj","hfadfj","aifjhadicggdejghh","hgbheeahahdgghhg","acbbabac","eieaa","chhhdg","fcaabgdddgdbibhj","gbdcbihbhb","igiaghjbcejhaibe","gdcahdhgcgijcg","cidihiihjgffbdiej","aeicbgejf","cbcdeajijfb","bghdjdfccgeeej","iefdeeje","eibci","iegdfa","dcgjiebfahaecjefaga","iagehajcdjhejfb","caeaigcjhefehiiea","eihe","ccebcgeihiab","hcgdhbadecb","bfbgi","hffeadbi","ig","aeajifhgdcajeichidha","ihbicjaiefgafjjhh","dbdjbcgb","jd","cbabdjeegfbbjbgi","afcafjjhcg","edh","eaafcbhdjecd","ehbaicebjgcgie","ccffcjighfgieb","jciabfgfheaeab","iaddhadcjce","efgbdaedaeibahaee","cgihebjgfiafaibjdaj","cb","heibdgjebjf","cbjjaceab","adddggiec","hddcdd","cehajgfeeiafcejadh","cbacfbcacjjf","adjcjcahgfjiahie","jiehcebggfhabbca","hgddgcgbd","cfbjefi","iijhejejgijbe","ajchj","hihhbcbbgicajbbfc","gjgjfhgabbg","hgbbejcdagedieeigf","ihcafhfdhfafjadfd","dicfihcgbcbheg","ddbgifgj","gcefhjgcidagdbjg","bchifiajeihibg","fegeagdfajcabaajcfhd","djefhjbegbedhceejiic","ebijicdcfehaadachjig","hab","hfgf","hedgdaddaai","dcgaijgca","jjhebhjefcccij","dficjfha","eef","eheachfbfgicihafhb","icjehbbdjfiib","ijgfiichdbjbadfh","dfdjegdabbgfigaaggf","aeee","dacbachbaababia","cbdfijj","ajaccibh","cjeaagjgfgfe","cjciacajecdhcd","fceagdchfcbfb","gha","dfjjjcajihgjjfaj","hhahgdaejeaah","hecbgebifjhihidbif","iggdcabbi","gijfhbea","bdbfcfafchgea","ebccfacgggigg","cihaijcii","iccebccfbgffh"]
- 각 케이스별로 반복 수가 감소하긴 했지만, 그래도 모자란 것 같다
====================================== case_time_limit1 ======================================
palindromePairs loop_cnt: 883600
second loop_cnt: 441330
====================================== case_time_limit2 ======================================
palindromePairs loop_cnt: 921600
second loop_cnt: 460320
3rd
3 생각
is_palindrome을 바꿔볼까?
3 코드
# 기존: Runtime: 468 ms
# 수정: Runtime: 292 ms
def is_palindrome(self, word: str) -> bool:
right = len(word) - 1
left = 0
while left < right:
if word[left] != word[right]:
return False
left += 1
right -= 1
return True
- 안돼, 돌아가
3 결과: 실패
115 / 134 test cases passed.
Status: Time Limit Exceeded
# length: 4000
case_time_limit3 = ["efedc","c","eef","f","edc","acd","fdc","cffef","fede","efb","bfbfd","bd","efccee","ebaead","fb","bfbdd","bbb","cffaefd","cbe","febaedeb","eaded","aaafa","ba","bcfdcfec","acbcbfb","cbbb","cf","ecd","deafdbb","feebbbf","dfed","baafc","fdf","e","defdf","dccfddd","bb","facaabee","ffe","adecbe","dbcacfba","a","edceaa","be","bea","eaddc","dd","fcccaeb","b","fbe","fffb","bffbb","ebbac","fa","bcdbced","bcdeac","bdeca","aeeeea","d","ceb","addcfab","ccfccfa","ebddbac","abbcddba","caebebee","bf","dacbcdd","aedccd","fadcaa","adda","da","dfebae","cdb","db","fde","fcbecf","efbdbcac","aaba","befcfefa","eafdadad","ebdadcb","ebddc","deb","aaed","edca","cd","cbecfdfb","aecd","beaedbcd","ad","ecabdb","caddbaf","aaad","ddf","badfed","df","eadbccad","fedcee","bbfaafbf","cb","af","eb","beecd","ebfda","bdba","aa","dcba","ddcea","ca","cda","fe","aafaa","bdfee","adcffe","afaddd","fdfeb","cdabcfb","aad","bdfb","ec","efebefb","cdfae","cbfebfbb","ab","fc","dcdcced","aaedeff","eed","effafba","acdabbbb","dea","bbfeabba","bacebcef","dfdbd","aaaecdcb","aeddacdc","ada","fdb","ceffdfa","dafbb","bfe","bbebdf","debacd","cfbaf","ef","ffade","bfafdc","bfebfec","acaff","cffaafe","daeebe","afcbadab","deee","acfb","aeadaada","fefaa","eeec","fead","fae","ddcbf","daeebc","abeaec","bcacac","deddffae","beeaea","bbfca","beaed","cee","dfebf","caabbee","bddeaec","fcb","cce","decdd","eab","fffcbd","bebfc","afefabcf","feebed","cdc","beee","dceba","dbaddcec","dcdef","edefacea","bba","dbdeb","eae","aefacaee","edddebb","fedcdfaf","dabfe","caef","ecea","aafcd","faabcb","dceaac","daedf","cedb","affaaad","cddeea","abcabad","eeacb","abeddd","abaabeda","ebcddec","babebfca","cedeeb","bdddbbbb","ffeeccf","eaff","efbeeee","bca","acffeada","cfeeaabf","beefdb","fbfeecd","ebebfa","ffadbea","cafafbc","defaadcf","eceadeac","cffb","bdddf","ecaafdbb","bce","adaa","adefe","bfdb","fedcbe","aadbfd","baffde","eefafbbf","cffdfef","cc","eddeafef","eaacabfa","eeb","defdaed","fbebafa","bfdead","ed","caffaaa","caefabca","bcafebf","bdfcc","aedfb","bfbdfbdd","bead","aabddfba","ccfddcae","ea","cabfdafc","facacce","aebcca","abecfd","caa","acbeecca","cfebed","ebedcfcb","eafbb","caebbd","ffcebe","ffaa","ee","fbdfdc","abdaedb","dbbca","bfccb","caff","dcfaf","dcdacc","fcabf","aaaeeffa","abfa","abc","ecccbd","daebe","adeecfbe","bcfc","fce","fddb","cccddeac","aaacbbb","bffdcc","dbacb","efbbef","ce","ceeffdfe","ccbab","edcee","dfc","cbbfab","cfff","bdd","cdffccce","eabfaf","cbfec","bbfdbda","bbfd","cecf","caba","ccbdaefd","bfbbb","acaedaf","cdca","decaa","cabdedbb","edbabeae","bfaea","afabce","bcd","ebe","afa","ac","ccedae","baaee","baafdbc","bbbda","de","dc","abdbcfdf","fbc","edbd","afccaa","dbdb","affeecfa","ffa","fd","bdac","fcce","aaebbef","eedca","faffc","feedead","aadfaf","aeabbecd","ddc","faaace","feb","beb","bafdfc","aecbd","bfba","dddbd","ffbdcfe","eaaa","ceae","ecdabebc","efefeac","feadb","ccfefdea","bdbdf","acdea","dcfefc","ae","ebafad","bded","cfebf","ccdaecf","abeadda","abce","ceabce","dbec","fbfdaabc","fbfebaea","febe","dbc","fcbb","fba","bbbfc","edb","dfea","bdbdfbcc","deac","bbbb","eff","aae","dcadc","ddabaf","faded","dcdfaad","adeecee","cefc","ebd","aeeccb","adaddfbf","edfeac","bffadaf","febdade","efa","bedeeba","fbbafdae","abddfe","dbba","cefb","ebf","cdbb","feccfe","ceaeeddf","dcedcab","aebec","fabcab","aedafc","bddb","dba","adabeee","becabccc","eede","adf","fbcafc","cbeb","eabf","aecce","efedfd","abaa","ceea","fdcb","edbbee","cfdeefd","ebb","affaceaa","eedfbe","aafa","bdbdbbf","afbe","ccccd","dbeaeab","ccedcc","cbfaf","dbaaeec","daff","eaaef","cddadbfb","ede","ebdcecb","aeaacf","bbdb","aacf","ccdfaf","dccddabb","adadcef","bddaabaa","ffb","ceeaeacb","eeebf","fbacfbfa","dcced","dcae","ccdaf","baef","faaad","cfb","eebdcecc","def","dfeddd","cafacaff","dbfffbb","ccfeece","dcdcf","ddae","fdaeba","aafad","eeafffa","deadd","eeecfd","eddbdec","febbcebc","cbbd","dbbd","ecafbeb","adaaf","bbd","cecffecb","aab","efddeeea","cedbfcc","afc","aaadd","dfcc","edbbbea","faac","fbaee","dad","bffc","ddb","bffdcee","bcce","fbedbae","cddf","ecbeff","acadeac","dadff","dbcfafeb","adecacad","dcddde","ff","bbfbcf","cbbeddad","ecdc","dfeccea","aaffbacb","beacb","ccfcfa","ffbca","dcceeff","bedbfacc","adaebb","fcda","eabeef","ffcecbfb","daca","dbefff","cfea","edf","bcfdece","fbae","feeeadc","baa","efad","fdefc","cbebaaab","aaacdaed","fdadcfff","fbcbdb","fdbad","cdedd","bbcfcaec","fdfdabd","eeafb","bab","acefbaa","dfa","ebabefb","acfe","fbcdadd","cffdec","dbabfaf","dcace","ddaf","bc","feef","edfa","dedd","afddafed","debefbd","aafedd","acbffbb","afddeab","dcfacd","cbbdeccb","cae","dfedfba","adcdc","fffacff","fdbabf","cdceeba","ebbfacc","dcf","edd","afea","cec","fefd","dfbac","bffcaabc","babee","efeabaa","dbcea","aeedac","adb","faabfb","fbafbea","accefbae","ffea","bdfceeda","adcdefbe","cffdeaa","bdeecbca","bcadcd","bde","dcdbfee","fdedeafa","cbfd","eacaebc","bfbdf","cacdc","fbad","cabdf","aadcdcd","dbadbb","cad","ecbf","ebcafa","cccfaecb","fcca","cecbefda","cebbf","bed","ddba","ffebb","bcefca","defeef","efeedad","cbcdd","ddbaccee","acaba","acdc","ffeae","fceb","adeeb","ccdece","ecfef","fab","dfdbdb","edfb","fbfb","decbd","abffdb","cdf","aadabfcb","edeadb","ccbbabbb","cdcbad","ccabffc","dbeddbf","dbe","ddfc","debdfff","aee","aadce","eefefec","badfebdc","dccde","cececcdf","dfedc","ddbeabb","aea","ddcd","bbaabef","ccdb","cabcdcbe","ecaceee","dda","cfddf","fdefcc","becc","bacbeff","bdfab","abe","cba","ddbcea","affacff","abd","aedfeacb","edaea","cffeabc","caf","babcddb","cafa","bcdcca","bcffcbe","fceabdcd","cedab","aaaddf","eebefa","dac","ade","eddde","efc","dbbdeab","cca","eeca","deeb","fafbeb","cfbff","efcbfba","ddecadd","bdfc","feafdae","bacfcedf","aeff","fad","aefbcef","cfceabfe","bbdd","faa","fabcc","eddabaab","afafffca","ffcfdea","cbcde","edebdae","ddeccccb","bfaf","bdfbbfab","ccbbcd","ebddaa","cbc","defcbfff","abab","dceabbc","eaefeab","baacbda","bdabc","defa","ccfadf","aeb","fffbc","dafa","dff","cdcdabcd","afecbfd","cdd","fdfcec","ead","ebba","bafcdb","aaeaaa","ccca","ffdf","bacdb","faacccd","dadabdf","baf","efcfcbdc","ceedf","fbafea","addfdad","ddfcccf","defea","bdcaadaf","acad","edbfbb","becfeec","cea","febd","ffcdb","caccaae","efdaeacc","bacbac","dccbffd","eabcee","badbd","eedda","cafeedd","bdddab","fefdd","caabdceb","afaba","acbaedf","cdbeee","ebecbbdc","eaccd","fcabbf","dbb","cadcdfc","ebabfba","fcfccf","eeadaebe","afdebdc","dcbeacc","ebcbaafb","afedceba","daeead","daace","ffbabedd","caabead","bfdfeff","cdfcebb","aebaaeca","cacfda","effca","ddecdab","cdcdf","eadbae","adcb","cbafaa","ecccdfba","bbcdeeb","eabccc","eaac","ddbfaa","ddbecad","ecbefefe","bbabe","afbac","feeb","caecccbe","fea","ceffb","eacbe","ffefa","fbde","dcceeada","cadafeb","decaddb","cfbbbeb","eeeba","deaecb","bbfdf","acf","adefefe","efdeadf","eddfad","beffcca","eabcefcc","acda","ded","dfeb","cbcbe","ecff","ebc","bbbdaedb","ddece","afedfab","efacec","ffcafd","afde","abcc","efd","ebeda","fddcddb","bdeadc","dacabbef","aaaef","bcde","bfb","dfbeff","efe","babaed","afcadfdc","abaf","ebbdf","ecec","ecbfada","bcdda","edeac","daccf","dece","eadbf","fdbcffdc","beddf","cdbfefa","daeeec","cefffcc","ceacebfc","afededc","dedcbd","dcc","bdddabdd","eabdcac","cbdcadc","aceff","ddcbaba","dee","ebeec","ccfbdaa","eabdbc","bdcaaeee","fcd","cbf","fcddbbf","abafc","ebbdac","adacacee","bfbf","aeeaa","efaaaaad","aeecbe","ccbff","bfcdbcfe","ccbdda","fbba","cabccff","bcabe","dffcda","aadaeeef","bedbdda","cedbeb","daf","eafdef","bdefeaae","affabcff","fdcddafd","abaaee","edde","eafdedb","efdcaece","dcdbbfef","eecaa","afdd","defc","baeb","edcdf","bcaecf","aacdccd","eeeead","ebafc","fcdaccb","acfdadff","bfceecf","eecafc","cecfaeff","ccadea","bebeace","ebcbecac","efaafc","baeeccba","fbce","aac","dadcb","cedeffec","fafd","bbaefc","dbebaedd","dabeddec","adbead","cceaeefb","cdba","eeedfefa","ceccb","cbefcffa","aacbff","beafdbbe","bbab","ccebfa","bfdedb","cbceece","aaaffbac","bafeeca","ffbfff","aecbf","dbfbdfd","dec","deefab","cbbdbce","adaffdac","fdedaf","fbccabd","cbdbbb","cdedcabc","dbbe","aabbae","fbeafefb","ceafaad","baabac","feeeee","aefa","acec","bfeeec","cdaeadb","befeffe","cfbdef","eaddcec","ffacffe","ceeafca","caacd","edccfde","bda","ffd","fbcfa","acccdda","cebd","aec","afaef","dbdcddfb","abcdfdf","adbddf","bdaeeae","ecdaadab","cdbac","bdefbbc","efaffbda","abdf","bdbfecdc","afbbb","edfeed","cbeafdcb","fabccbd","cbfaddf","eebeff","cdbeeedb","ddcddfc","afee","cbebed","eaceebd","abbfb","efae","eabe","fbbe","cbdeae","bcebacd","eac","efdbecee","ecbce","dceaed","bbffeacd","cfd","fbbded","eeeeccb","aacfc","dbfbaae","bfbdeacd","eefc","dcbeef","ffbbfa","ffeaddd","cfeba","dfcf","fbbdbefb","eeead","fddeffee","efcec","cadfae","acbbdcab","efeebfeb","aaf","fcbfdc","dcaaeb","debde","bebdc","dbccaea","bfefae","befa","ddebacca","ddaceee","fdd","dfcaadc","ebaca","afdb","dbdabf","fbfdb","fac","dfcfd","bfdefc","ddaeabdf","dcfacabe","bad","eccfcd","ebfbd","cfaccf","deebcbc","eda","afbb","afcbaad","adbdeb","abebeffd","eafdcba","dab","acbddde","cdabdcb","becab","bfafdfb","cdbc","bafafe","fcdca","eeea","dedfca","bacbacf","ceeae","fcabcbf","dbeeccd","caadaff","adbe","cbdacf","feab","abceafac","cdddef","cedeef","dffeeec","bbea","edffce","ecaeec","bbcafad","dcfacdae","efddbefb","cbddfff","ceddc","cddbb","cdaebeab","eeaed","fcead","dabfa","ccfdfc","fee","ffdddbd","bcefdcd","edafbedf","aebfeaac","fcdd","aef","edeaad","bbdf","ebafa","bceee","fbcf","caaa","adcfefe","bceaacd","ececef","ebab","afaedcab","ebeeb","cdcbdd","bdeeb","aafaddbf","adfde","dafcc","ccdfbbee","faea","fdcec","bbfcb","afcbfd","aadffdee","acbaea","ccfec","dcdaa","abbd","ecae","bdafa","bceff","dcbdf","fcfebdc","adfdfe","febaf","eddbec","aaa","bbeb","dbafab","cbbfd","ffee","deaebb","bbecae","defceaa","bfbc","eefb","aebecb","babd","deafdfbc","dafb","bdfaf","fcac","fffcc","cffdfd","cdaabaa","feeeeddc","ebff","acbcfda","cfefcf","addaed","dcfde","ecabaa","bfeef","bffcbc","faeeffa","aaaaa","debcccde","afece","addec","bbeafd","cbeabfec","beca","fdffec","ceeea","dafbafdb","cbec","faeaced","fbdfee","bfcbbfcf","afdffd","bbcbeb","ccbcacff","ccae","dcab","eaddbebe","caebaaff","cecbedc","fecfafaf","dcadae","aeede","aed","cdefadb","fdcadfd","bddbff","fefa","edbc","febcfed","feccedc","ebace","afeb","eaacec","fcdeed","cafbbcf","aeecfc","fdaae","cbcaea","efcd","fcec","bcafeefd","aedebc","bfd","edeceef","dabdfcc","bccabaa","dfcea","cfcecfe","aeafebbd","adacf","fddeb","ebeeda","cadc","afccbbc","acfa","dcadadee","aafdb","caada","baedaac","eecdd","cdab","dfcba","bbabfae","acdb","bdb","fdbeca","badfb","eeeeeb","ecbdcfee","daddb","ebfc","adaedfc","dade","bafff","adbffe","accfdbe","aebb","bdbedd","efcdeb","efcddbbb","adaaefea","acb","dbbbdae","effbfeef","afbadba","abf","efbabb","dfacd","cbcaceda","eec","aeeb","abaedf","abdebcb","dafbfdb","cecbdcaa","bfbac","ffbdfee","bfdf","aceef","decaba","dbae","aaadee","edfbaf","dfcdfeca","dafebdfb","fdeeaed","aacbcbbc","bcf","fdaf","eeabc","dabada","afaa","afdeffc","bdbbd","adcc","feed","dccfa","fdcdfaa","baddcbfc","bdcdcdfb","abacde","acafdbc","faeafef","bbe","ecac","bfaaccfc","ceedcc","befcdfe","ffddaa","aebcbec","eea","dfe","aaccb","edafba","cbcdbadb","ebcf","faccfacc","adedce","bddfccc","bcaffac","dbceeb","dffc","caeefe","cfcff","badacffc","bfcebaef","edebcfd","fdaa","ebecfcd","bebecdba","bfcdf","fcbbdbc","bddbdeb","dcbeedc","eebcdbeb","bfaeaaff","dbfbfbfb","caedbace","eedcaef","dfbdbcc","edfafc","adc","ffdedab","ddbdbba","cdfef","ccdbeee","debb","dbfaa","ebceeb","abed","cdafaeb","bdef","bfdfd","cfaeeeda","fcfaaacc","ddcbbb","fbbd","bfcbdbc","eedafa","efba","cbffdf","ddcba","ffaadbaf","aefdfe","cfebedc","cbecdcd","cafcafea","efabdc","efebdced","eaebdbd","ecdcdbce","cebcff","caceebf","eabcce","ceeedb","acbccb","ffffa","fff","dabdf","dcccceda","afacbc","afced","aedefc","abee","aaebdae","fcde","cccfeb","adbc","dddccdda","ebefece","aedfa","dbfacada","aedd","ecddd","fbddffa","dcbfee","adfabda","fddabeaf","ccffd","aaecab","fbacdc","daa","ecfcd","ecdfcb","bdaddf","bafedaf","dfebb","adaaeac","faae","acbeeccb","bceaac","cab","fadbdaf","dfbddfd","fabc","eacfb","aaeee","cdfeed","bfedfd","ababedaf","aabcbeba","bbaf","aede","befeace","fec","dcefcae","cffd","bbfac","aecbb","efece","ffff","fcc","fbca","dbcbf","dcfadddd","edfbcde","dcd","eaefba","ecc","cdcfd","dacccbd","fdfddc","bedfec","abffdacd","eaedaeaf","ddbeacad","eced","afaffea","cdfbafbc","ddbebedb","ddeeb","beccacf","ecaf","caedddd","dbfee","dfffc","bbeebfaa","ffeadcdb","ddeeebcd","afcbd","cdbcea","fcfafbcc","ebceaced","dbdcd","eefabaa","cdfcd","fdcfada","acccabe","cacfad","cffccefe","bfdbeefb","bdfebf","aeaa","fecf","faaddc","dbee","fdbdcb","aebcd","dddfd","eeeeffb","bcfb","abcdc","cbfdeef","acbdcdb","eace","eddc","bbc","bcbc","cfaee","becbb","eedadbbd","dbdaccad","ddbadcbd","eacabffe","effb","ecaabead","addc","dabec","dafd","bdaaeef","deafffed","befdafe","ebabdfce","ecdbacb","cfe","fefdccee","cdec","abfafa","dbbfd","cbcfcad","decddcf","bbbbea","becdc","bbbde","dcb","baaffaa","deaecbd","abbfc","cfbba","ddcdafa","aedfed","fbdbfcdf","ebadc","aebbbec","afccadd","cffbbb","feeffbac","aaadba","ffbfeebd","cbfad","afdaae","fcfeddcc","aabecdeb","ebbfbbbc","caaadaf","cfbaacb","fcecdafe","faaadd","bfae","adecae","afedebf","dbaeadaf","abfb","fdfdcef","dcee","eeceee","fabdc","cfcd","ddeafbdd","edfefcb","fbdaadf","daeed","cecc","fefb","ffffbdd","eebbafa","edfcbdca","efefade","acffecb","efccce","fdfd","dddebeff","defd","dabcc","bfebcb","bdddfec","addeee","dbfa","fbcafa","aedebdfd","cddabc","acab","eedafc","bdbcefad","cacba","bbbafefd","aafceafd","adedacec","cbaebfbd","ebfca","faf","fbefceab","deff","fdeebbe","cfdddb","afd","dcbcfadc","abfda","ffca","afbcfefa","eca","cfeaea","bfcc","ebacdc","afca","acc","baecaddf","adaefee","cffdddcd","ece","baeecbb","ccf","cbddcedc","befbfc","fadcbcf","fca","faebccfe","cbfdbabc","fddcbae","aadae","faeefacd","cfbde","cbcb","edbccae","fbb","dcfff","cbdb","dde","ffbeca","dafdffa","fbccbe","baaea","aadcdb","efac","eaefd","aecfc","dbefbae","feeaec","cbda","caafe","bbedf","ecf","eedd","cfbaeba","cecefabe","cbfea","bdfd","baed","adafacf","fccbf","baafbfbe","affcdcd","ffafbacc","bcef","faadbfa","fddcbfca","eacbda","cbafe","eccbdad","acdbaae","befbfbdf","cfeadbad","cddbacf","feba","ffbcb","cde","cfdcfba","bedcb","ddfa","bbedcfa","abba","fcfcdc","ddcfdc","ebfba","febee","bbfefbef","eccb","feec","edcd","ebcaead","cbdbd","aaaeae","fcf","ddbebc","ddbbfaa","eaefc","efdcbbc","fdcade","dcbbd","aabffed","caebce","cdcdff","fbfdfae","fdefedfa","dfdbaed","bfbaaacf","ddfcefc","fedbbef","faeba","cbebb","eade","abacabb","dacf","adeeaad","ebbaffc","bebd","dafbcfb","afcbeac","afbcaba","beda","fefff","dfdb","efbdddd","eecce","dcccac","aadacc","eadea","bafcea","daefcde","bdeab","cddb","ddffb","edbebbd","bfec","aadb","dbce","fffefbc","bdbcabaf","abfcacd","adfdb","eee","acdae","acfccbdd","ebbb","fdaceace","afbeaca","abbfcede","cebca","aecfddce","cdfaffac","ebdb","adcdbbec","aabab","efcbffae","fbbbbbc","ecdadeb","bdcceae","cfffea","bdaeeebd","adfdc","fdaca","bcdfa","bbcaebb","dbbfb","bcbfceef","cdcaef","cfbbdbdd","dddcadfc","fdccfe","bdcb","ebde","efefecbe","fbf","bcaeeff","edbfee","dbfbe","eaaaeee","deaddcfa","cdabfddf","bbdacdf","adecec","bdaadacf","dcbfdcf","baffdb","faacf","ace","cdfdb","dcbfc","abefcbb","fbaedda","fbfcb","ccaabf","daaef","bbdfddf","bedfefc","affcccba","caaadfd","aadfb","feff","afacb","efdaee","bbac","edfbf","aaccd","dbedaaab","dddefafa","afb","ccd","cbee","eabdecdd","eafeccd","abddd","dfdddacf","fdaec","cbdbaaa","bdcedcd","fcbfc","cfcde","caeeed","acfbcbbb","aeaec","eafdead","abdba","faeffd","dfebdb","edaaedd","bbfdbfef","cbbeaca","bfbebfee","fcbabbee","eadfb","fccacad","beddfcc","affaeee","aaabcadd","feacbef","caebdada","efedcd","cedbc","bceec","adbddbfe","dbafef","bcaf","bcdbeafa","ebda","cfcf","dddacad","fddfc","ebaad","fefaaee","bbffcda","ffbdff","febfbdd","cbeecf","aba","bbdfe","dfccabf","cebcfe","daabacf","cddde","dca","fbdce","acaaeb","bffddf","cfcabf","abcfcda","cddcc","dfadb","eaeedb","cacaedd","ababc","dcdbd","ddbccc","fbdb","accbed","fcefdda","bdbc","efcbbca","fceffbdb","ffadc","beaaaf","fada","cadbfc","acdebedd","fddcfb","acbbabd","efdfda","befdf","bebea","ebaba","beddede","ffafb","dcdefd","eccd","fafc","eabdfaae","aececcbd","dbeff","dfb","bdf","ffcbdccf","fffdf","babcefbc","eedcc","cdfccaf","acdedf","ddeab","eefd","aedcdcfd","dcbeab","dfd","bcbecdea","ffbaebb","beecbeaa","addbf","daffe","fbbb","dabe","bcafaffa","dbafcabe","aababfdb","ccddda","aafd","fecaf","eebbbfad","aafffb","adadadda","bddcbdc","bdbdd","ebaabe","fedb","bfbd","bee","bafdea","cbeffdc","fbadae","ffcdafbe","bbfe","adabeceb","abdfadba","cafdb","bcdbe","decbaa","fdfede","dfebc","bcfefc","ecbd","fbdddbdb","ddbceb","abbbaad","adffbde","fecccc","eacdbac","dcadca","efbdca","fbdfedae","fceffa","defcfdb","addcbc","fda","fbcbe","ebac","ced","bffbedef","dbda","facbcb","dbbdd","fbac","aaaade","ecbee","dbadef","eabafdf","fbebeac","bffbfc","dcfee","adffdca","dcfd","fbcbb","dafabdda","dbbeede","fcfbaeed","dcebdf","bbdba","fceeac","ecdcd","eddef","edbfc","caaeee","ffaec","ffebefcd","fdaaef","fcdeaa","bcda","eeacdbe","aadfd","cebf","febfac","abea","acddcbed","adfbcada","cdfaa","fdafcb","ceefddcc","cbecf","adbfe","bccffdcf","cecb","afaaad","fbafb","cdafbdc","afcab","bfdbcdc","afaabcbb","efeeaeeb","badffcd","baacfb","ffdc","bffe","cddbf","addcdb","fadccaef","dface","ddfddde","fcebedf","bdbbc","aebafc","baefdae","eafddaa","babb","bcad","afec","edafc","bddec","aefc","abccdadf","ceabec","cbceaa","dddebd","bcec","cafebbb","ebebec","efbaeb","ddaeade","cabffb","abddf","efddf","ecbfc","bbcadf","aebdeeae","babbea","bcfdeb","edab","fdebbeb","fbd","bbfdffaa","dcdbfb","addafdb","bfc","dbabfeb","bdfba","edfbee","afeaaef","eabcf","cedd","fbfc","aff","dacfbaa","ffccffb","bcffafd","cfdcaece","addce","adfbab","acaefac","cfebdff","eaf","ebdcb","efffe","ffcafc","aeebd","eadacfd","bdfdcb","bfdd","cac","dbbdfedf","afda","edacec","dfdca","cbefa","dbacbb","cccf","ebec","cbaabdd","bcbae","feafea","aeacbed","dfbaaeb","dddcba","eafd","cfa","fbece","caeabdbd","fefeaa","feacdccc","bebeaede","ddd","adadbaf","ecccae","dbab","bfefcb","febdfcc","cbff","badfc","eada","ceaade","bdaece","babeca","ccbcbae","babcfa","cbdcffcb","efdfffad","cddfdee","cbabaa","ddffeea","abaddb","afcaad","cfcc","edbfbbee","fabcfaad","dabdcdd","cecbcce","afcdfa","ddadd","dbcb","fefffdf","efddca","cabab","bbbdccca","affbcae","abfeecfe","afabafb","fadccdc","cecbfbbd","eeadd","eecabccc","bbdbaac","bfebffb","dfafcd","ffddfccd","becdfdd","bbbecec","bac","caceebab","bedebd","adfdfc","eddffb","becea","ecefff","bbeaceae","bacab","ffcbdacf","defbbfef","ffae","fdaedebd","ebffcc","bafed","bacdff","cbbddf","bddebdc","cabad","feddab","ceeccb","aebdecc","cfaeffa","bcc","debbfef","ccc","cdedc","baedded","bdee","eba","ecafabe","fddafc","aaebe","afed","eecaadd","ecefdfb","deaafa","dacd","dafbcfde","bbddfcc","caddeeeb","aabfe","ccfbaef","fbedafcc","abffca","fbeadd","dcfbacfe","daefbb","cfad","bbebdbf","cbcdaae","aabda","accdeeff","ebacaaa","bbcdceb","fddeeb","aecea","ccbbbc","ceaecb","cfccce","ffde","dada","effbf","efca","eebea","fecdfe","eeaeadc","cfcceba","baec","bebeeeff","cbcafbaa","baedf","fbdee","fcfe","ecdb","cefccda","deaaaae","affdf","acacfddb","daefdffe","cddd","fdddd","eedcb","eadceefe","ccfdbf","eaebbee","ebeddfb","dffcbdff","bcfdacf","fdfcbde","eaa","bdebfbb","efefcbd","beeca","bcdf","ccaeb","edadbbb","bfaef","ecfc","bdcaa","ccdadeaa","dfecff","bdaebda","dfdec","fadf","ffaefedd","beaadb","bafb","abefd","edcbdbf","fded","efeeacba","cbcbaffa","cccefe","affacaa","aedbef","bdfe","febaafce","dbadf","bbbddcda","dddec","bfadfbef","ccfe","ffeeac","eddaaced","fafbf","efebaa","fbec","bbf","ccbeddba","bfeaaccd","dffe","daedc","decaaab","beeecaba","faafae","cbfeac","affa","dfaddad","dcefbcdd","befbcfe","dfddde","abbedcb","eecc","ffbbef","cfef","ddbddfaf","eeeeab","abdc","bbcbb","eccadb","edbb","febbfe","afedcd","ffeacefa","ecdaadee","daec","bacec","acbefcdf","fbdcade","dfdcdace","ecad","ffdfbff","dbabcba","eebf","babdf","edff","ebdab","eaeac","dffcbd","badaccd","bfff","beebf","ccaffcf","cbabdba","efafad","dbbbe","bfed","eeaa","feaffbb","bcadeeb","edcb","eabbdcb","bccda","cedbfcdb","cfc","cbdad","bfde","fdbee","efaf","ecbedfcd","eeaecca","eabcc","bcabfdf","acbe","acabb","ceadfd","edceffad","ccfcd","faccaff","dafefea","eacafeab","adfbfbb","abbdd","dddfcf","cfecda","dbbcddf","cadfbcab","efafa","bfdfb","badcf","cbce","facd","cbedae","bbcdceaa","edaec","eead","befccecb","bcedeefd","ebce","ffebac","cef","baafbbf","edfffaff","baebddf","ccecffa","cefbfda","eccac","cadabcca","cbef","fcadfcad","feffd","bcdbeb","fcdcdd","fdaeddcb","aeeadda","bcccedb","fceaacd","dcfec","fceaead","baefdff","fcbfe","ebcefe","acfccfc","abadac","eacf","edafaadb","dcddcaa","aeeaeaff","daaedc","efabdac","eddeafe","fdac","eebebfe","ebece","face","fecaaccb","caced","cafd","eddfdfba","ecbcddc","caebcdbd","aeecbeb","beaebe","afabb","abccadd","acff","dfaccdae","efbeccf","acccec","ddccd","cbbfadae","befcaf","affaa","bbedd","ccb","abeff","acaf","cfddbfb","bfffea","cecdd","daacfbcc","ccfb","ddfacacd","bffbdbf","aaec","bdfcca","bfcdea","bbbdbac","cedaecd","ffdeae","dfdbe","accdbe","eafaf","dbfe","bafefee","cbcadd","ecebc","cbfc","cecdaff","ffecf","defeada","dfbaa","ccafd","bcbfc","eccc","feadc","fabfe","decabfc","fafcddef","dedbfced","deceebb","eddeff","feeffece","bdfbbbbd","ebdacbb","afbdcc","fcbbbdbc","fdfbeb","cbdfbe","bedcda","aebfb","afbab","effdbfd","dce","cdceda","ddce","addb","bffadbac","cebdbaeb","efdf","aecfccef","ceebcfea","afccfbf","dbcfceb","fffdcae","efcdbe","ebabe","eafaadfe","ffafdc","bdffb","cdefeace","adfda","beececf","eeeeea","adfadca","dcbbdedc","eceadfc","ccadb","febbe","accbbeb","bffcbf","cafbdced","aaffb","bbbaafac","edaafad","dfddee","ebbeca","dccebad","adbf","dccbcdfe","dfabaeb","dbcaabd","beefa","aadbdade","cfaebc","cfeb","ecb","ddbade","aaccecd","aaceb","facaeeed","dfefbafd","adeccecb","afbf","aacdceb","fadcfed","feefc","fcaccbdb","bcdfabb","ceaae","cfbfcc","dfdf","fafdaadb","fcebffcf","cff","daebb","bfbab","bacdaf","fecaadb","dcacd","effeae","ffdbc","afeefc","fcbdfaa","eeabca","bfdac","adeeeebd","ddbebad","fbcae","bbff","efcdc","ecaa","afac","ffccdf","cccddce","eacccfea","ccdf","cfecd","ccac","dccac","eaddbcdd","eabcbb","fecdbfda","fcbcc","fffbdbb","efebcad","dcffcfdd","efcaace","acacfff","ddaccad","beafddef","fbeea","baeac","bafac","cbcbbeca","bebae","bbccd","bfdaeb","ddebea","caacdfdc","cfbecab","baeddfcc","fbddcfde","dcccceec","cefeae","dacbddb","edaaeb","bfbcdedf","cfceedda","daabcee","eefdfdbd","affcbfcc","acfed","deabeecf","ddceaedd","aaabe","fced","abfce","daffbe","cbabeba","adeda","feffbcaa","fdbbfebc","daccffdd","bfaaffd","cdfdc","cfffb","fdfff","bedddedb","cdbcd","bbfcc","cbafb","cbeaed","adacafbd","bbaaba","ccaab","ccafc","bcdde","edfdbbe","dcdd","bacfecf","cbfe","dbececed","adfed","fbaaded","eafdfdef","edfe","decfdfd","feda","aaaeb","cfcbcac","edeebad","bcafb","afadbf","aedc","afadcec","afcea","ddcc","cdabeca","caea","cdaefaef","cfabfeee","cfbfa","dbbde","abb","fbdcbc","facefac","ebbdafe","fdbdbc","eebcade","fedbab","eeddedc","affdbff","fbcedfa","eefffaab","acbeb","dacbaddd","eccff","fbfafa","ddcedec","efdbcff","bbbdeeb","beaffe","dfba","ebaccfae","cfadfaef","dcbcccef","abebca","fbcc","bbbddfcf","edfaeda","abcbcffc","efdccdb","fbaab","efdc","afadc","dfca","adfaade","addcec","acbb","dabeeccd","bcaccab","eeefdee","cfdfdd","adde","cabacedd","cdefae","adaecfb","cbeac","dddfe","badef","afefd","babec","bcdbabd","eadbfdbe","abff","faddcc","fceafbf","eedcbbfd","bedffdef","acaeeee","ebdcbdb","dfdcabb","cedbd","dffb","afffcbfd","eefbceba","bfbca","bbcd","efebfd","eceba","cfeceddd","cadf","cfffdf","acdfcbd","efcbae","fccfcaad","cefffdeb","aefeee","eaafaede","dfbefbeb","dedcceef","afddeae","abafeb","adccdbe","aade","dfcb","befcaae","fdebbe","caabfa","eadbbdc","cbaafca","badacfdf","dfdd","fef","bceeeac","caaea","efdad","fdbdcdf","abbf","fcaddf","aaabaee","cbac","bfbeebe","fecfab","caffedeb","beeaedee","bbefcafc","efccfadd","ddcadbb","eebdeaea","ebadd","bbbdbdfb","babcbb","aacbca","fecdada","ddceeac","fdfbfbee","deedebc","cabfd","faefebde","ddcbdc","aecc","bbfcfc","fcbbdda","fdedfef","ebaebfb","edda","ccdbecb","baddbacb","cdbcdbc","efdcafbe","cefddbb","eeee","aedffdf","bdfa","dfaf","fccdd","dabc","adbccf","beba","cedeafce","bebcdf","dfce","bfabf","fcecbf","cbeefee","fafeef","ffbac","abecc","bceaced","adeebce","ddcefe","bfddbdab","cfabddb","eddbbecf","acccbd","dedccbd","faacacdb","aedcfbaa","aadabb","daabbb","cfcafc","fbffd","afadcdc","dcfdf","ecdfcfc","bffb","aefdba","aeeadeee","cdaacf","fefabbfa","fedabcaa","bbdbcf","bdddb","ccecac","adfba","fdcf","dabddda","feecefb","fadbd","fffadda","debeaf","cffebbd","dfadc","bdeedd","eefdacd","bfefcdac","bbcf","baddfce","aefeff","dbbaccdc","abca","bcab","abcf","bafa","eeacadb","faaf","bbbbbaba","eebfbce","eeafccf","eefbcfa","edecde","dccda","cceadc","dbdaab","eeededb","cdbbba","bbec","adce","fecd","dbdbdb","fdccdd","cdfbfa","bcdebcd","eebdfa","dcfbac","dcefff","ceedfa","cfdee","edadecbd","dfbfcd","afaeaae","bccacbee","cfedf","fecdaccc","eded","eeedbab","cbaef","cfbc","cbeacf","ebfa","fadadc","dadb","eccaba","aadafd","fffaffab","eaaeabb","deacccf","cedbcf","efdbcf","daaac","cfabafba","cbaa","dfdedcf","fdfc","badefbe","cefcbb","bfdde","ffcfaaed","bcabaea","cabfdca","fcfeea","cebfc","fbccebbd","bacadda","bacb","abbeeff","efbfa","bbfbb","ceccaa","effd","fdfdacab","fbeffcf","bbafd","beefba","bfbfa","adfdf","fdffcad","ffce","bef","aeceefa","cffbbafe","eabee","cabcfec","bcbcacf","caabcc","fbcd","faec","fbbf","dcfebced","cadfa","febb","ffbfc","abefcfdf","afdcee","edeca","efabcdca","beeee","cbfa","ffceeb","defabad","bcdbddaa","dbecee","feaafdca","deeffc","addf","abdeab","daffcaef","ecddbd","ebfbefae","abcfd","efaef","bcbabfff","bccd","dfbe","ffeb","faaccab","bfbe","dfafdac","afaafbec","ecca","bacfebde","ceecd","efceab","bddbdd","afebdeb","cfbf","cddbbf","fffcfb","fbfeeee","babfaf","cabcfdcc","eeababdf","ffceecca","bffeb","ffbadf","edadc","baabebaf","dbeedbab","deeefeac","bdccfa","bfcfd","ecfb","ebfadcce","aaadefc","aaffaaf","fccecc","adcfcbc","bfcd","bebcab","fedfefcc","ddecac","fbdbdf","bacde","fbfcfb","edbcfeba","ecdaafd","eafeffb","ddaeccf","aca","bfddfdfe","ffffcd","bbef","cfabc","adeacb","daefdada","eafeaba","ebbdcca","bfceac","cbd","cfebca","eecbdc","dafe","ddeaf","adafaae","dcaaceee","eafbda","bbce","bbcba","beacaebd","bdc","fdfbee","dfabca","bfa","fbfeec","bdff","bbaa","ccbcae","acca","ddaeebc","cfafa","acceafb","edfedefe","affab","ffedbab","eeedefd","ceaccadb","bbefeb","fdacdd","aafcfa","ddaa","faacbbc","becda","aaebdcbc","ffbbfdf","efcee","fbcfbc","abbe","ccffab","babfbaa","aeeefcad","ceecaf","acbbcdcc","dcbceee","edcbdfec","dfaccf","eafb","fcad","ebbaa","dcdbbd","fdcba","bfaefbbb","ddcfff","adcfecc","edef","bdbcdbb","cdeeadc","aadfef","abeef","abbacc","ebaf","efeb","ecefffba","baaffedb","dfdaa","ffcbd","afbaeff","cdcff","cfaeeefb","ccfddcb","eaaecc","ecfbeef","adcde","fbeb","dbeeeecb","cdadceea","affea","ccbfffca","dbbad","adcbffe","adddfcc","abcdd","abbbcef","cfcdcff","edfefffe","eedb","dadfbff","fbbdcb","fbbfc","efccdc","ecbfe","cedaaf","cfec","ebcbf","eceacf","dfccc","adbdbbd","cfdde","eebfbae","accfdfe","daefaefa","dffbfcfc","bff","abdbaa","acfeaadc","fecbc","eeccbb","faccb","dbeadac","befbeda","cfffc","beacaf","bcffd","aaabda","aeed","bbbadd","eeaafde","dbbeeebc","acdcce","efcebeb","bdedbd","bdeeaf","deaeeffe","daddfadb","bafcb","cedeaadf","bafadcd","bddbbcf","bfabccc","fbaabff","ddccbddd","efecad","fbef","afbd","bfccbcb","caedbeb","cedffdec","afce","fddfeaf","beafc","daaf","efbbb","afbfeaf","dcddeac","cbbefecf","ffeeda","cfdbfde","abfec","dfbf","aefecabf","fbbeea","ebfb","bcbbb","ebcdd","dbcafb","fbade","adfd","cacad","cfacddbc","afbcbf","fdefbbd","ddaccdee","bfcdcda","eaeb","eedaeab","cceda","ddaee","fdbc","eceacb","cadfef","dacafc","fdcc","eeabdd","bbebae","ddeaea","aafedce","fbfaecc","adbfecc","afacdff","cafec","afcbabac","dfdbfea","ddeaacfe","fdadeecd","ceddb","eeed","bcabcf","cbca","badc","eefeee","baea","bdfedea","ebbfe","aeebce","dccdac","cdcbd","dacdeac","ccaebccc","becacabc","ceadebc","baeabb","aaffbb","afedeabe","dccdb","ffedeb","dfcfcaf","caecedd","dabda","cacaeabc","feddf","bcbaccaa","fefdbbec","ccede","ccfaf","bcdfdfcb","cfba","ccaded","cbfda","bdfddbbb","eadccb","cfdaacbc","cbadeac","cffc","eacdbe","cadcdddf","aaee","efbcaaee","acbfdbc","acdeeaa","feaaaccf","ebcb","cebdd","cadaca","ebeafcf","ebdeaf","fdbdeeff","beeafce","bbdeebac","dbeede","fddea","ccefeb","ceddbe","fffdebda","fffbaca","feabbc","cddeefa","bcbcabfd","efeebfd","bacebdac","feceafc","aaecaddf","adfeef","feececaa","ffedafcb","cbdfcaa","ebbce","bcecef","ccab","dbbcc","edbdea","eccfb","fbffcdbc","fabddbbc","fbdfd","ffedfbcf","cbbceac","bffd","afeaad","edbbfba","bacf","dbcde","ccdcc","fdfbcca","edfc","eccaef","dced","eeedbcbc","dfcabeac","dffecad","aacbfce","bbfebd","dedbadce","ebdbcbb","dfbdbaed","cceccf","adbfcf","baebafa","aecadfad","fbfffd","ccdadfb","caee","acace","edade","bafe","edccb","cbcce","ccdda","dbcacaaa","aebccddf","ebed","eafdadc","acaaaf","aaaeaf","debf","fddddbab","faeecf","eafcbffc","ddebc","ddefccea","feeedef","ddcdb","ecdeedea","dbffdce","ddda","baefd","aacdd","ffbddaec","aadbd","dafaab","dcacaa","fdabb","cffbdcf","ccefed","afede","afdad","fbaaf","bdfead","ddbf","cdfafcf","cccdab","cdef","efbdbbce","ecabbbcc","ecbfded","acfbbd","caacefad","faedfd","eabdbbd","bceecb","ebbcda","cfbcadd","bebf","aaccddaf","efea","cccfccbf","fdfdd","aaaaea","bffbd","dbbaac","eceacca","fdedfada","bfeffcbf","eabc","baebf","cffffef","eddadeff","eccfadca","aaeaab","cbfccdd","debbafb","bdcfebfa","adec","caad","ffebfb","afcaa","adedfc","addbdb","dfaad","efacba","addbbcb","ffdb","bbca","dbcbbfa","cfaa","cafddcfc","dbbedc","dcaeeb","eebecfad","dedee","feffdbff","abdeedc","eadddbb","facceff","ecdfdffc","effdded","eaeeae","ebadeb","dfcca","cdaabdc","afeabb","bcbb","ebeffb","acbffde","cbbcefee","accbfebe","dbf","dfdfbb","add","ffbb","cccbeac","afdfaeed","bccaaac","dcfbdaf","dbdbd","dafbbde","dcdfcdeb","cabba","cbbc","feddccdf","acefdb","dffcca","bfcbbe","befceedb","aacd","fdff","fdbeb","fdfafced","bccdb","fccefae","dbdfd","bcecbb","cdcdbcbe","ebcdec","dcadbed","afefa","ecebdad","acebb","dfae","edeafcab","fdefedbd","bdfbffa","bfafc","dcbaeb","cecafee","fbdd","cfecace","eccfcf","ebbaf","eccfbf","bbeccd","ccfedfd","abaaacb","cbbabfbd","cbfecccb","bcfcfbdc","abcdcccd","cbaddcda","ceccbd","afefed","cbfaef","deeedae","adcbe","aadc","dfdcaa","eefbbfc","ccdae","eaeaaf","ffcf","adbde","dffdae","bbeafede","aaacd","fcccc","ceebdbbb","ddddf","bcaefd","ccad","bdafbdcf","ecbbcbf","fdcbedbf","afabddbd","faaaeab","fefdffab","dbcdbabd","acdef","fddeab","dcfcbbaa","faeace","cccfdfc","efdd","bcfca","cefa","adbdbabd","dedbddc","baaaca","daafa","dfbebbf","dfefb","cbccb","acedaf","addda","bddfaf","eeefecfc","beeafc","adaaea","ecedc","defbcace","eeab","dcbc","dcec","bcecbcae","fefecbc","ccbfbef","aebc","febfbc","aebdaa","faebbd","dfdddd","ebcedfb","eacfee","aefffd","afedca","eafbcebf","dacbdccd","dadcbdab","adddfcad","edbae","bbefaede","cfacde","bbafcda","aaafcdbf","ebbea","fdebff","acdeebca","bbba","ffbed","acfbbe","becbcc","abaeca","fcdad","beaeeef","cefeedcb","fbed","cbbabde","cdfff","afdba","acefaad","fcadabeb","fbdbeafa","adffa","aaddfb","eeae","cdbfebae","ccffdeac","efbafcd","edfedf","eccae","adedefd","bcabdfac","deaed","ccddfd","deacfc","aeebfc","aeccffda","ecbacaf","eccbd","becd","ebaeb","bdccbca","beebeae","eeaabec","ffbbbc","cbfcedc","cdeaf","bccbb","aaeddfb","beafffb","eddddb","ddedc","badcb","cbbff","eecadd","cfaffeb","ddbbab","ddccbeba","ecacfc","baeeefc","bcdcff","fffcdb","bafbb","eabd","fabaaca","dbfab","dcfb","abedcb","adbac","dfaededb","abdabfde","adcefaac","faedbdae","dbbafccc","faecb","beceb","caadcba","eddfbfcf","ebef","dacef","affbcbcb","dace","aeffb","bbceffea","dbacf","ffcbfab","ebdeda","edad","cdedcc","bfbaf","cdcc","ceadfcab","dedfdda","ebaee","efbbfa","bdecff","ccccb","dbeec","caead","dddee","aaffaac","bcbdeac","ddaebf","adffcaee","dfefd","edbadda","ebeeafd","eaeded","bbeaacd","bffbfcd","faca","efab","ffddefcb","fcacfe","fbabcdf","cdfba","aafeacbf","febcfd","aeca","fcdaaec","dbd","bfaecfc","fbda","ecbbfbdf","facabc","afeafecd","bbebb","bdddfed","fcfef","fdcfaa","feeeebc","eaef","fdeb","aceaa","bfddefac","cebb","fcebfdb","daadbf","bdbacfbb","fadadf","fadd","befcffb","eabfa","cbfbfddf","eefbfeca","ccdbaaab","fbdfca","abffedc","bacbd","fbcaadef","bdfdaca","fdecfbe","fdbfa","ecacfb","aead","fefde","abdbba","edfeafed","dfbdc","adcddfc","abbc","feaaedce","fdbef","fcfcee","eeef","abeeeefa","dcdf","eecdfb","fcaa","afcfdf","afaf","fcfcb","fcefec","acaeacdd","cebacacb","ecbbcb","efbefffa","fabdebdb","eccaee","fadef","ebbde","ecceef","decd","efbb","fdddf","deaabd","adcaeb","fcaff","ecadbbdc","acabeede","dbfdabc","eecee","ecafddc","bcffabe","afab","fddfdbd","cacceffe","ddaaedfc","dfedecf","eedccf","cedfceae","dccf","ebdeabae","dbfbfd","fedab","becf","dabcfbfb","daeb","ecbeadcd","bfecf","cbcdedfa","ecdbdeec","fdecaf","cdfdcbbc","bbadaaf","deabacca","fbeedc","bdaedb","cdfca","aaafab","daafc","edaca","aadfedea","eebb","dabfdcbb","acabece","acedcd","ebabda","caaba","efdcbad","bceab","eeeaaf","dfcebdd","efadfcae","eacbc","ffceebbf","acedaade","afdcbeb","bcebaaab","cdcbcfed","cbbdaefb","dcbdc","fdebdab","feebf","cfbcdb","bfeaaba","efbdb","eecfdae","aecefbfd","ffecaeac","aabdbfce","abfacc","aebdee","fabcee","dafacb","cefedbce","cedafba","cfffeeea","bcb","cfcccd","eaefcc","ceedfdc","fdadbe","fcbfb","cdabddf","fdfebcbd","bbacffa","fbbadce","cdecf","ecee","aadcc","faab","dfaebd","adceefd","dbaaeb","faebec","ddaefdec","faeecbff","caebadbe","deecdfe","bfffabc","cbedbcf","faebaaa","edcece","eaaebfc","ecefee","ebbafae","cdeeef","dbaaabe","dbccd","fcbfd","eefddbcd","eafed","beddc","cffecd","cadde","ecfd","beccedd","eeadfadb","eaeddbae","ffbaac","fcdeffef","cabb","aceb","acefdd","efaada","cbffd","bebbce","afeecb","aaae","bafaecf","dcdcefdd","dceaafee","ecbfd","ababe","ffffdd","babf","aabdeeeb","cdcbaa","dcddabfc","abfab","dfeaafce","ecfefda","daaeaaa","dbdf","cadcd","ddccf","aaefcc","ebdaedcf","fdcfcd","cfcfad","badce","eacde","caaceeef","cedbeaa","eeedef","baceca","bceefa","effeb","dacafacb","ceffdff","ddca","bacfeac","bbcccb","fdbf","cfceee","fbbee","dcaecd","bdca","befe","decab","aafcee","dadd","deeac","affbead","edbffadc","cafca","ceeffc","fcedcc","cacaa","cbcbdecd","acbd","fedecf","aaccfbfe","efddef","cacadd","beef","daddfce","eccee","eccbb","febffab","caede","cdfebbb","cdadbcdf","bfbdab","dcafff","fbdaab","fafa","bbcefeb","daecedfa","aceaecbd","bbbbb","cffaac","fdbedd","edfaf","baff","ccddff","aeec","cbfdefe","bddae","adeab","aaaaef","feffc","bbaea","ecefac","baac","baabbb","afffcaed","ebcce","adfbaad","facecfc","bedbebe","daabbc","cdbeabce","afeaf","bdedfd","bec","febfdea","ceff","bdadbfc","eecb","efccddfd","caeebca","fabdac","bebbfcff","cbad","fdee","afbbcaa","decdbfe","fafdbaee","daecebab","caecebbd","bbfcd","ceacbfde","cbcd","fecabbed","eccdcdec","acdf","edfbb","adeef","befd","fdcaf","bedc","fecdafd","efda","bbbbccbe","bdadba","ccdaafeb","dbde","decffcc","efaec","bdbcbffa","bbbd","aeefecd","baceacec","fcfbbc","ddadcb","afdebcd","cacbee","febade","ccdedda","accabefb","cfdddfae","effc","bcdeb","bfdefeeb","dcfbdd","fadadba","fabedfd","ccdeea","dcccd","bbaffda","cdcebd","fbdbbbea","cebfebba","caaefd","bddeefbe","bbbdecfb","feddd","dfaadecb","dafce","bbda","dbfdcd","fdaeec","cfadbc","dbfdeeed","bdacb","dcdacd","feadfb","fccaeebb","fefe","ebbcdcab","ccfcceb","eaabfa","bdeefb","dcecef","eeaee","aaefd","afdfa","fcfbcde","feccb","feeecf","cffffa","dae","cffcec","bccdf","bdbfae","bdcdf","fcdcf","cbbbb","dbfdeca","eeddea","dadfbacf","acfcd","ddfb","fcef","beefdbed","cefcd","fdcdff","fcdcbc","daaeaca","efcef","facfdcb","cdefdcd","afddb","fcedfabc","dbdff","bfada","bfbbceef","affefa","bcdcf","facbd","fdecfcef"]
4th
4 생각
- 어쩌지…
- 어쨌든, 반복 수는 더 줄이고, 팰린드롬 비교 연산 속도를 더 높이고. 어떻게 더 줄일까?
- palindromePairs loop_cnt: 16000000 , 7.5987403 sec
- second loop_cnt: 7998000 , 5.2122952 sec
- 실행 시간은 2초 차이로 크게 차이나지 않는다.
- 문자열 붙이는 시간 자체는 짧을까?
- 아래 테스트 결과 문자열을 다 붙이고 모두 배열에 담는 시간이 더 오래 걸린다
- 팰린드롬 체크가 오히려 시간을 줄여주고, append가 생각보다 시간이 오래 걸리는 거 같다
# 문자열 붙이기만 테스트
def second2(self, words: List[str]) -> List[List[int]]:
start = timer()
words_len = len(words)
if words_len == 1:
return []
if words_len == 2 and "" in words:
return [[0, 1], [1, 0]]
ans = []
checked = collections.defaultdict(lambda: False)
words = collections.deque(words)
loop_cnt = 0
i = 0
while words:
word = words.popleft()
j = i + 1
for word2 in words:
loop_cnt += 1
word_check1 = word + word2
ans.append([i, j])
word_check2 = word2 + word
ans.append([j, i])
j += 1
i += 1
end = timer()
print('second2 loop_cnt:', loop_cnt, ", {} sec".format(end - start))
return ans
# second2 loop_cnt: 7998000 , 8.7617033 sec
- 교재는 이 문제가 트라이(trie) 장에 속해 있다. 트라이를 사용하면 비교가 더 빨라지나? 아니면 트라이 써서 더 빠르게 하는 방법이 있나? 어쨌든 문자열은 앞/뒤로 붙여봐야 팰린드롬인지 여부 체크 가능하지 않나?
| case | is palindrome? |
|---|---|
| “a” + “ba” | O |
| “ba” + “a” | X |
| “ls” + “ssl” | O |
| “ssl” + “ls” | X |
| ”s” + “lls” | O |
| “lls” + “s” | X |
| “aabc” + “bcaa” | O |
| “bcaa” + “aabc” | O |
| “bcaad” + “aabc” | O |
| “aabc” + “bcaad” | X |
| “abc” + “dcba” | O |
| “dcba” + “abc” | X |
- 현재로서는 방법이 안 떠오르는 걸 보면, 지금 실력 어딘가에 구멍이 있다는 것! 뭘까?
- 트라이 자료 구조에 문자들을 모두 담아보는 것? O. (4000 단어에 0.010268800000000008 sec 소요)
- 트라이 구조에서 인덱스를 저장할 생각? O. 필요한 게 인덱스 값이니, 어딘가에는 저장 필요했으니까.
- 단어를 뒤집어서 트라이 구성? X. 생각은 했는데, 어떻게 활용은 모르겠다.
- 뒤집은 것과 팰린드롬 여부를 어떻게 코드로 풀어낼 수 있을까?
- 책의 설명은?
- 단어를 뒤집어서 구축한 트라이이기 때문에
- 입력값(=word)은 순서대로 탐색하다가
- 끝나는 지점의 word_id(=해당 단어의 인덱스)가 유효한 인덱스면
- 현재 인덱스와 해당 word_id는 팰린드롬으로 판단
- 생각은 했었는데, 안 될 거라고 생각함. 왜 안된다고 생각했지?
- “a” + “ba”와 “ba” + “a”는 다른데, 단어를 “ba”를 TrieNode(“a”) -> TrieNode(“b”)처럼 역순으로 저장할 때 모두 커버가 안 될 거라 생각했다
["abc", "a", "cba", "ba"]
root
| |
1--a c
3--b b
2--c a--0
0:"abc" -> 1번 인덱스 만남 -> 3번 인덱스 만남 -> 2번 인덱스 만남 -> 최종 "abc"는 "cba"와 팰린드롬
1:"a" -> 1번 인덱스 만남 -> 같은 인덱스로 스킵
2:"cba" -> c -> b -> a -> 0번 인덱스 만남 -> 최종 "cba"는 "abc"와 팰린드롬
3:"ba" -> b가 없음 # 이런 경우가 문제일 거라 생각했는데... 책 풀이는 이를 insert에서 미리 처리한다
- 0, 1, 2 케이스는 생각했지만, 3번 케이스 때문에 안 될 것으로 보였다
- 책 풀이는 이를 insert에서 미리 처리를 해두는 식으로 해결을 했다
4 책 풀이 코드
class Solution:
# third average in 100: 0.033489098999998745 sec
def third(self, words: List[str]) -> List[List[int]]:
start = timer()
ans = []
# third loop_cnt: 4000 , 0.010268800000000008 sec
for idx, word in enumerate(words):
trie.insert(idx, word[::-1])
loop_cnt += 1
for idx, word in enumerate(words):
ans.extend(trie.search(idx, word))
loop_cnt += 1
return ans
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, idx: int, word: str) -> bool:
node = self.root
for i, char in enumerate(word):
# 2. 문자열 길이가 1인 경우는 insert에서 단어 삽입 시 자신을 제외하고 팰린드롬인지 판단
"""
트라이 삽입 중에 남아 있는 단어가 팰린드롬이라면
미리 팰린드롬 여부를 세팅해 둔다
"""
if self.is_palindrome(word[i:]): # 단어 자체가 역순으로 들어오는 경우
node.palindrome_word_idxs.append(idx) # "a" + "ba", "d" + "cbbcd"
node = node.children[char]
node.val = char
node.word_idx = idx
return node.word_idx
def is_palindrome(self, word: str) -> bool:
right = len(word) - 1
left = 0
while left < right:
if word[left] != word[right]:
return False
left += 1
right -= 1
return True
def search(self,idx: int, word: str) -> bool:
result = []
node = self.root
"""
단어를 뒤집어서 구축한 트라이이기 때문에
입력값(=word)은 순서대로 탐색하다가
끝나는 지점의 word_id(=해당 단어의 인덱스)가 유효한 인덱스면
현재 인덱스와 해당 word_id는 팰린드롬으로 판단
"""
# 3. 문자열 길이가 2 이상으로, Trie 내부를 탐색할 수 있어야 한다
# "abc" + "ba"와 "dcbc" + "b" 같은 케이스를 먼저 확인
# ex) "cba"는 Trie, "ba"는 word로 탐색 시작
while word:
if node.word_idx >= 0: # 현재 노드가 단어인가?
if self.is_palindrome(word): # 단어라면 팰린드롬인가?
result.append([idx, node.word_idx])
if not word[0] in node.children: # 다음 단어 구성이 안 되면 종료
return result
node = node.children[word[0]]
word = word[1:]
# 1. 현재 탐색한 Trie가 단어이고, word와 Trie의 역순 문자 길이가 같은 경우
if node.word_idx >= 0 and node.word_idx != idx:
result.append([idx, node.word_idx])
# 2. "a" + "ba"같은 경우. insert에서 미리 처리해둔다.
for palindrom_word_id in node.palindrome_word_idxs:
result.append([idx, palindrom_word_id])
return result
class TrieNode:
def __init__(self):
self.children = collections.defaultdict(TrieNode)
self.palindrome_word_idxs = []
self.word_idx = -1
self.val = ''
- 케이스는 크게 세 경우로 나뉘는 것으로 보인다
- word의 길이가 1보다 크고 word와 Trie 내의 단어 길이가 서로 다르고 팰린드롬인 경우
- word와 Trie 내의 단어 길이가 같고 팰린드롬인 경우
- 위 두 케이스 외의 경우. 가령 word 길이가 1이어서 Trie 내부를 탐색하지 못하는 경우 insert에서 미리 팰린드롬여부를 체크해두고 word가 붙었을 때 팰린드롬이 된다고 본다
4 그 외 리트코드 솔루션
# leetcode_sol1 average in 100: 0.016300982999998936 sec, 4,000 단어에 약 27,610 반복
def leetcode_sol1(self, words: List[str]) -> List[List[int]]:
start = timer()
loop_cnt = 0
d = {}
# 역순 단어 테이블 생성
for i, w in enumerate(words):
d[w[::-1]] = i
indices = set()
for i, w in enumerate(words):
# 개별 단어를 좌/우로 줄여가며 팰린드롬 확인
for j in range(len(w) + 1):
loop_cnt += 1
prefix = w[:j]
postfix = w[j:]
if prefix in d and i != d[prefix] and postfix == postfix[::-1]:
indices.add((i, d[prefix]))
if postfix in d and i != d[postfix] and prefix == prefix[::-1]:
indices.add((d[postfix], i))
end = timer()
# print('leetcode_sol1 loop_cnt:', loop_cnt, ", {} sec".format(end - start))
return [list(p) for p in indices]
# leetcode_sol2 average in 100: 0.030206388999999945 sec, 4,000 단어에 약 61,750 반복
def leetcode_sol2(self, words: List[str]) -> List[List[int]]:
loop_cnt = 0
start = timer()
# 0 means the word is not reversed, 1 means the word is reversed
words, length, result = sorted([(w, 0, i, len(w)) for i, w in enumerate(words)] +
[(w[::-1], 1, i, len(w)) for i, w in enumerate(words)]), len(words) * 2, []
for i, (word1, rev1, ind1, len1) in enumerate(words):
for j in range(i + 1, length):
loop_cnt += 1
word2, rev2, ind2, _ = words[j]
if word2.startswith(word1):
if ind1 != ind2 and rev1 ^ rev2:
rest = word2[len1:]
if rest == rest[::-1]: result += ([ind1, ind2],) if rev2 else ([ind2, ind1],)
else:
break
end = timer()
# print('leetcode_sol2 loop_cnt:', loop_cnt, ", {} sec".format(end - start))
return result
회고
- 중첩 반복문으로도 풀리고 트라이로도 풀리는 문제였다
중첩 반복문의 경우
- 더 줄일 수 없을 거 같았는데, 짜잔! 퍼포먼스는 더 좋았다…
- 단어를 앞/뒤로 붙일 생각만 했지, 테이블에 역순 단어를 넣어두고 단어를 줄여가며 팰린드롬을 체크하는 방법은 생각을 못했다
트라이의 경우
- 역으로 단어를 넣는 것까지는 생각을 해봤지만, 이후 트라이를 효과적으로 사용하지 못한 것 같다
- 알고리즘은 자료구조와 어떻게가 대부분인 것으로 보이는데, 둘 다 미진했다.
자료구조 측면에서
- 그래프보다 직관적이지만, “a” + “ba” 같이
트라이 내부를 탐색하지 못하는 케이스에 대한 예외 처리가 미흡했다. - 자료구조 통해 가능한 것을 최대한 활용하고, 그럼에도 안 되는 게 있다면 어떻게의 측면에서 해결할 수밖에 없을 거 같다
어떻게 측면에서
- 자료구조 생성까지는 아무나 할 수 있지만, 완성된 자료 구조로 문제 해결하는 것은 아무나 못하는 것 같다.
- 돌이켜 생각했을 때 이 문제 풀이의 어떻게는 어떻게 나왔을까?
- input을 분석하여 문제가 되는 케이스를 나눈다
- 케이스별로 공략한다
- 책에서는 3가지 케이스로 나눴고, 이 코드를 보면서 나는 아래처럼 정리가 됐다
| 책 | 책을 읽은 내 생각 | |
|---|---|---|
| 1 | 끝까지 탐색했을 때 word_id가 있는 경우 | word의 길이와 == Trie 내의 단어 길이 |
| 2 | 끝까지 탐색했을 때 palindrome_word_ids가 있는 경우 | word의 길이 == 1. word만 붙였을 때 바로 팰린드롬이 완성되어야 함 |
| 3 | 탐색 중간에 word_id가 있고 나머지 문자가 팰린드롬인 경우 | word 길이 >= 2. Trie 내 탐색이 가능하고, word 길이 != Trie 내 단어 길이 |
# 3. 탐색 중간에 word_id가 있고 나머지 문자가 팰린드롬인 경우
# word 길이 >= 2. Trie 내 탐색이 가능하고, word 길이 != Trie 내 단어 길이
while word:
if node.word_idx >= 0: # 현재 노드가 단어인가?
if self.is_palindrome(word): # 단어라면 팰린드롬인가?
result.append([idx, node.word_idx])
if not word[0] in node.children: # 다음 단어 구성이 안 되면 종료
return result
node = node.children[word[0]]
word = word[1:]
# 1. 끝까지 탐색했을 때 word_id가 있는 경우
# word의 길이와 == Trie 내의 단어 길이
if node.word_idx >= 0 and node.word_idx != idx:
result.append([idx, node.word_idx])
# 2. 끝까지 탐색했을 때 palindrome_word_ids가 있는 경우
# word의 길이 == 1. word만 붙였을 때 바로 팰린드롬이 완성되어야 함
for palindrom_word_id in node.palindrome_word_idxs:
result.append([idx, palindrom_word_id])
- 결국 세 케이스는 아래와 같을 때로 보이며, 세 케이스를 통해 모든 케이스의 팰린드롬 여부를 체크할 수 있다.
1. "abc" + "bca"
2. "a" + "ba"
3. "ab" + "cba"
- 여기서 배운 게 있다면,
- Input의 케이스를 분할하고
- 분할된 데이터를 보고 자료구조를 정하고(하지만 사실 이는 정복 과정과도 관련이 있기에 풀이 과정 상 유동적일 수 있을 거 같다)
- 케이스별로 정복한다.
- 다른 리트 코드 풀이를 보면 충분히 문자열 그대로 풀 수 있지만, 책은 트라이 공부를 위해 굳이 트라이로 풀이한 것 같다. 같은 문제를 다르게 풀이하는 이 자유로움에 현타가 온다.