411. Minimum Unique Word Abbreviation[TODO]

Version #2 AC Version



Version #1 Brute Force [TLE] Version
直接暴力得出所有dictionary string 的abbreviation
用target的abbreviation和set里面的比较
找出最短

class Solution {
    private int minLength;
    private String result;
    public String minAbbreviation(String target, String[] dictionary) {
        Set<String> dict = new HashSet<>();
        minLength = Integer.MAX_VALUE;
        result = null;
        for (String word : dictionary) {
            dfs(word, 0, 0, new StringBuilder(), dict);
        }
        check(target, 0, 0, new StringBuilder(), dict, 0);
        return result;
    }
   
    // Enumerate all possible abbreviations of given word
    private void dfs(String word, int index, int num, StringBuilder sb, Set<String> dict) {
        int len = sb.length();
        if (index == word.length()) {
            if (num != 0) {
                sb.append(num);
            }
            dict.add(sb.toString());
            sb.setLength(len);
            return;
        }
        // for current index -> compress or not?
        // not compress
        if (num != 0) {
            sb.append(num);
        }
        dfs(word, index + 1, 0, sb.append(word.charAt(index)), dict);
        sb.setLength(len);
       
        // compress
        dfs(word, index + 1, num + 1, sb, dict);
        sb.setLength(len);
    }
   
    private void check(String word, int index, int num, StringBuilder sb, Set<String> dict, int count) {
        int len = sb.length();
       
        if (index == word.length()) {
            if (num != 0) {
                count++;
                sb.append(num);
            }
            if (count < minLength && !dict.contains(sb.toString())) {
                minLength = count;
                result = sb.toString();
            }
            sb.setLength(len);
            return;
        }
        if (count >= minLength) {
            return;
        }
       
        check(word, index + 1, num + 1, sb, dict, count);
       
        if (num != 0) {
            count++;
            sb.append(num);
        }
        check(word, index + 1, 0, sb.append(word.charAt(index)), dict, count + 1);
        sb.setLength(len);
    }
}

TLE
"onetwothre" ["rkaromrcbl","cgdqnbwoom","icqwawtgux","egrsqhqmdg","mpeqhehtfz","fntpyxdoev","bpysavnyvp","rztggzislg","ndhsychnkx","tmvgcwsqxl","ghtavqzdku","duxqlvvxer","jvsuzwihvz","pwedmdanxi","hkrjexfwki","jeomlkizat","swpmnxaifk","jlecvorgvm","ukcddxpdvj","eaijhjzexy","zyzlgrnjdg","qiwkjffays","cepthmkpiw","wyxcveickl","euuwvrqtte","rqodvucfrx","ftwidrlvcr","yulrlrjeaz","nsmsyqlbip","cversuexrs","sxoxjsjiql","lvltjbbibe","jntrxysnth","vgjpovdigm","wadvlanmab","njnyudpakg","yaoaexeffb","ljcvvizzat","onovwwafjd","mibcnmgdch","pcdalztmug","lhnrkihtsj","hmrgddbgxz","ykerkcirnt","bgsvmqlhle","fjfopyhuxm","likhegxmry","tnybravwig","ayccnuiiar","xnslfgdwff","leivjyejzs","ggcvkzrkfh","ycninyoqme","viaeyugryr","avwmkgvolr","rztqnynkaq","wfblaildla","pcibbcnkvv","bqmnorzfty","alxbxfdflo","mmbjxetggn","tshbgnwujr","bqqkhgfbsh","vjwirxojpg","oprjyasewn","lmkwrcuewh","jmtznciylt","znioetuyrp","avmgbtoabp","hqcgdwezws","vbsxcnjiyc","dbpyoqssdg","lmllmyztnz","qjoxpylmou","tfotxdjqwq","zwgnwmkkkl","ykypesaksg","karblvxqwj","hfabvikusr","xzrgqlretn","sekpoaxpqw","ojocklcynn","uwgwyskqix","rewsfjqxiv","hfszylbzoa","tszvsoxffc","jetuoinngo","iwldqqqtgq","ugzvwndttq","tqgmczwsds","zlmbrftzwt","ilfsfgprsu","izxuftidre","czampnjeki","vtmtwljddl","bkwhbpoqzc","irykbeqeae","wpbjuosruf","dbecaxjyfc","vappsjvxds","eszeynzxgk","vyryylckvd","dxgrsrqtzs","grklncpqno","hdgkizpstv","kuelsplstn","jioihzdsjv","lkvpximomy","zgbazdwerq","mzdnunitps","crdwyctvmx","vkcxtvrolp","ewvyugbnxt","iptugjopof","uvsbhslgsz","efaazcmgqn","odhwoyubqz","tkiphyvhzm","dlfompwbcn","uthdbqnqhd","hrymmxhkyz","gqwnjhrzrv","rgmbkkrsij","eckhliblev","ukbsuficxy","wxsbudpayi","efkiscsapg","rthxnxxdqr","vwqhmbmoew","uhaxwxxlvv","flmcdceers","gudnihidnq","uglwjqfvnl","jpvqtyuwou","jgpcxtdfzc","qruarlfctn","lyqenkusvv","bxlwxddwok","ycpqxwyrpn","vaoatwogqz","hlyzjaszyv","kkfaqqlxqt","gnxoaynrsx","umgohdcjtu","fbogoqpzic","gmgkbmycfg","hmtcwvlcak","bbioreajzt","hsywmtrzwx","wkxiaugaru","eoffbgnync","eqwcuqfrvv","jshvxcsjta","uoilmsdphn","mmlefkhjlx","wzrqmywkre","qknpbnplhy","jqajvorqzk","wxaaihkmgc","ofipipoaeb","ivvtcwuwpu","qlaphulysp","vdlvmgogun","kckgpqrgde","upzwzebpot","uhmwprqujt","qsqrwnwbmm","xyfrnzgpbf","yeuydievju","sadhocohse","pgtlzezzqi","qxmjjjodol","mzpitgkhqk","cqesfbgyeq","igkzzompsv","eelpodtvkw","xspozoxitm","xcatlxravb","bahvvdejdr","jwsnephxil","wubbiwjxok","sjfeprnxmg","impdvqccmg","sywdrujoim","ahhyqokgkw","llivqxfomd","izgljwaosi","lwejzmfmum","kvdgepwjiv","wokufytuog","leyrhwlode","qwujqyhdtq","augomiegzc","dawdmfiyfi","clltonasyw","uwmyftdzlc","hpbuccisxv","dqvbeiolpi","qcoelfgekj","vuhljsyptt","tnsyzjkepq","nojrlyocpv","jkmurokagd","ktsczgdvxg","tuwuamhqcs","pywkgsfrzn","pqdcqkayrx","wfcafldbdw","nzzmqjjwnt","pouzrvsfmd","anhitvoqsg","zgjxlhvxal","mmkkoxllpx","tlaibfblba","jseepbrzqn","escpqfplbh","xcuqdlpohe","dinlfopmak","quhtycfztb","jabhzctkem","kvujljlxlr","ieermvpola","lnvjsbwtyw","tuvpedtgrt","ovndpydtea","dqgjcfvwxo","mklxjejzal","ttrczgappv","umchzdzslf","pqmqsrxvle","aovakofbqi","xugswhauhl","kcavggbgdn","fnfyvugera","mjnzmsnwjz","tvkbjhacit","ytjtsxqgta","ogokbhswpc","lwahoewpbk","jsanvhhaxr","vbsvoqobpf","wcrftfiapu","alzcaypbto","jbpttunqpz","idtykgeqwj","igluzaaxzh","mfrmalgoia","puuromirde","evtrvgwgiy","fjxerafngh","kpbxuuyjzs","bqsitqnpge","segagpipmk","fhewkrwplc","irdzhdbyjf","oixcddxfcn","zdjvpbkfvu","uxnkrmjegj","axwxqzdfkf","wdmjibssgi","hongmgsbah","qjsyehxrta","pfcuuhjloj","jvwaziwnab","yrbvaahjbd","fyndtzmibj","uiymzzdyau","logicyjcta","ksjsrlegnh","zegnghadux","ertotwgjly","ljpumdhjbs","wbathmuxyc","gwypioivhb","gixjjncnwu","mjghnftald","suhuakvnqe","obzbiskgnl","mesfhxqljd","rtcjwyehqd","xwltmxwzct","yqniboesdh","gntuznwfpn","aydtyvatiw","djxxksfdqg","iksgynlrdm","bzrxivhpsz","pdkkzirtfd","tkuqcbkenr","gkbdlrbcdh","owkzgyagnj","qtmoxotxiy","ffzqbmqjin","abppepmpve","evkabwwspq","krlzskvqwu","vduzjsbbad","elexmftoyw","herjtdxbyp","oyjmlggphc","babpsjzohe","msjtgjjucx","uuryitndpd","wqmbgfugib","suoleojzmq","pugzyazgxh","xzmeyzocec","sysyhioxgb","fouzdaioge","qtaanuabjw","mlpftkoyaq","vepkrzewot","ctpsagubff","mjatcvmmxq","tedjnxpciu","cyjgyujqln","ubbyjaxvyb","mspzftzowj","vwrzouuxfc","apbnjvfodg","owlcxtmrth","cpydpratev","nqaogjqvng","plvogrcqux","zsxtjrscyv","hukvkgsykv","vycweckuda","iarmqiylpa","bkfdhoobbk","uwqztqvfgp","audiizdwrd","fpmxlrudsb","mdlcojdrwi","nzdtulpqlr","spswxxbtup","ifklvrtude","gmrqaodzzx","bsjtcrlqhe","hofpmpygsp","lrsrusvnpc","pqjsoiffqz","wszfxozeyb","ckehyzmjbf","pupadvmozw","yutvysgcqe","kkigqkxtun","oebmzvcfsj","rjshkqobov","ncezdpfmzc","vdiiqowixs","ysvthrllwi","hggcviftsd","gtlpdgiogj","kehvffaips","azzcejappt","qmqvzyhxxo","uqbzkyprgw","cecznqjzzz","agsanizkbf","lgbaolcaoo","qwpljtrsxf","shfkvmehfq","ejkwnjqmkm","psbtexhpsp","udcmjlswqi","cdzybavecf","qrrcvobzim","pyvtlmhezp","ojhkmbwbig","vcqmxayuoj","tahxzdzath","xwosdwaxmp","xydruzkofs","xpbdfgoljc","pfapltzqiy","yzjlcbkdci","jevjtsbzym","oerbhzgfvp","filwanhqgy","lkgetjjnob","lecbgepxfp","gjdgvdptre","cubogrhiox","mbykbhxrsk","cgndmdtftu","oqnasbumze","lanqdsrgnn","rxlvhwbjkd","uyikygxhde","dvusokvpkr","njgtwcjyxq","webvpgduhe","jooxtqepko","ewntsinmfr","fgslnktytv","cwewkdsjlv","jmcrwdvyvs","rcjfaontaz","rsmshzldhd","khtqwgbftj","flsazxaoye","psielzdtpo","pzyhbqtowc","fbzarwvlnx","uzdjxohgcb","nuorwwvjhs","mxzhfvdokq","cucqwqkkfv","kmhqqdaory","hoyldihsio","mogjomdtno","ylhryaemow","vtbzrctzes","ygukxqfygb","tyysmdnamn","uxnegiiqbw","mzoymgtkiu","kahtfqbjoo","jnuzljrdjq","xekobsrrex","rxuuyymcuq","excfnzzlfb","hwshqvplck","esyrsgubpx","dovvkqcodn","gpnuqhvxax","mkwxxdclrj","rhtcqckgjb","crcigwavmv","bgxncjdepo","qyhrzlgvhh","ovmkptayle","yqsnqzuhbb","meqnotlfgv","ehayslvfuh","dfiuslnbxx","qjnmogwzxh","joavqnclpl","cfpolcbebu","asaykbtrkl","ulurlfborn","bujrqboxht","rybjznkwhk","krhdfjnyvm","itqshtdgtg","rokgrfgqxz","dcccmdcxpe","puqjfmifiz","tgweqfqmmx","mkvrkvydca","vizbpqkjhf","zlroochyzw","krhxtnxplz","zwprzgyfwj","cswngmrxwd","wknaaplxvw","uhqzqprvmv","ebqkgzwnvn","karblpzvpl","orcbziqwfa","jxnxftbkns","uawdhzawcx","blgardomfd","setsynkucs","vygzfqncpq","mabnuxpoqo","hzkcqnohfw","fmenyiloni","aynxdvhcgh","uvenozbufc","oyufphgnck","chpvoaphdr","nacybsmood","wdkowlsnnk","tnndfpmxgm","iqxwziqopl","vjndylkfyf","huytmldevq","bfepsmzack","lypmgcghzq","vptjwhqwvs","pntjuxlvph","nvdgeclbmm","rqnorxfpon","rzpewlwtel","ooshukzuvj","imvrwgzimm","glysoltzku","mrhipjkptt","wdsxxyxstv","tbgzgwbweg","jngczisbth","ytgadierdi","emupezpzgo","zoxhfhjche","jbrtypitgc","nhlywdyrkl","ylvvuxnbla","lykverisbj","hwjnelonec","gioxpxxgpi","jygvkbbegt","vdroxspahq","qmccvxeurn","knpycthhaq","tdouqmouzo","ckqqlghgur","laplacxfgb","cbhtzwriiw","njgmousyky","qjiutmefey","qvxfcfpuie","nzhksaaqnc","ulgtrnzmnn","svcxfhbcvp","seqwyekxbp","dhtutxsgjj","ybonqyzuiw","dcnrqgtqub","klvukpseel","unuybutscm","vltdcylylv","elnaqgclhw","xnfrbpabgt","ehpqviebwp","biqkxbwyju","ltwmerrqmj","ixczhninbz","byemsryyxh","kyxqmpeyun","kosfnzsipm","gjwckqvgpa","nioevqzklr","llixglamff","uowucdoxtm","gmziwaqijq","wpahffpfba","ozcepkzkuk","hjwfonfhii","kqpvseducn","izqqtwlusy","zwaaugmmjt","dfxitqdhvm","jexsxvyvql","coqyiwagvc","hsswztfqlz","dtdbmyxnuz","sujbwhzaaa","usoojybqhl","vturgkplxi","imektsgofv","hdbchklaot","snzvwerkzh","apdxsfjuhb","japucmcwwa","omajpxifto","yrnjvjkoan","vgtkwsohsj","uwwftgvzek","bixzrhudrh","zmkvlxorqc","dshikdwbzr","opovhdfjkq","jhaiiktzro","zkwyodutsz","nvosfngpns","orbkxdwjkx","napykdiriu","fhkyrpeeru","nlshczrrne","jixnmqfqjx","klnthfgqbq","hvzozhfhrh","bjjssxofhm","nwuoglclmz","cnzbvhjkjs","qlgbbbhzeb","cjnekqhepm","dvmjxyvqty","smqtsokate","psrziqcrfq","gcbelqerwv","kijvtufiqn","zqqpkyocxj","siswmjmpgc","mmyjhomxgz","seqaauoost","vaqtvcfxst","eewwqfcuum","myuzcjxazc","mazuiyacbq","qgmcwoejyu","exfsobtvll","toyjbniqke","tdokycpwry","bdpyjscdsa","lwlrjwskds","ubswlncnzb","gsmanpioft","hfumimelre","muxattjsvh","vfrltokoiz","zrnbtppgbv","nimdtkdnnt","likbznzcod","wyanqgypjn","idehxrshne","wnfngkexox","hqdshcztkl","cnvaulbfnx","xnitliqxju","ypmwodatah","zjgzkwvpki","vaiitbalti","hanhhecibk","eekknqqpyf","cwcebhcowy","wlodfidqps","imbwmxocmn","mkqdarumdp","ogztxktnel","aymyrisavj","zcgmsmvrvp","wkvgctblut","vvdffjzevo","nhnivcxsxr","potjpikdpw","lwbofagifd","gdpugqmcmd","hywghbbofe","gmpbavzewc","vquezoxpcc","qqknwllhot","xvlnapisvk","nqjgbbbdsc","zbyvtsgxrx","afdscdtuig","jyxxrknizw","tyrwhfdqpb","rrsaxmuvcr","ljmwjeplbb","gkewrecgkp","dhouzordas","acjpzkmgjp","mqaceydfqx","nhtzcaesnq","ousmcebttf","eztcdtlryf","fgpebkrpst","ukeatvruux","phrjvpmjme","mlgmidhqlg","bniqmkzvhj","jxbpevetde","jnjxlvegak","aglacbsozc","qezotaizij","oebucsszbw","mwtovusrtm","didlkdgbrm","yfxuwfdzqb","wgmhqmxfzs","lkdqfpgvih","aftnhojohf","zqjkqxylhx","weokjmxgyf","rqbidpwxun","ebnwlwdkkh","yicdgrlfht","exadvjqzhm","mihrnsianx","pavwqcedqj","vznfjxndph","nrzyoliqin","seousvpnwv","nrbkyxknfh","qhkzpqqqux","ppjrlhfzhu","lntztijwmp","mskzuecwda","inlqiuezhx","fzdixbsntf","izqwlumkku","qmkaiccwdm","ykbawvjykl","zfwumgzulx","mshemudgid","ftfukzyjfh","dtrtmzlber","vfztqetnvh","kqbbudzctq","sbofalvjiz","eqswuygmpq","feqfqbvgeq","jatlzcojyf","fjotwkrowr","igfevujeuz","essfkyvpjt","qbuqtwzigz","ogyacvsxrk","jflgfguqfj","tpwcdxbbpq","qabtvzzndx","momvgzaqlq","ckhxerxncz","oucryibndu","ltlfckaeyq","fekladjiwz","lejinimira","orrnojpjvd","tmajyvacfy","waoxnqzljk","mxmouagoxg","tsviocdyvr","ykmhdedosd","plxjtoecil","pgzbsdflal","vnzbxtvocz","qbdidfxrbi","grpcnxfzrx","spkbqquncx","yphvluihsa","djsgegvgav","vrgumtfaru","evexrtqawo","moixxsnsxc","bsjcmpwcuy","wubpdalppo","caznrihobl","auiemgkhue","gzuxqfhodf","mjafhwxjfj","krorwsntgo","fgpdpnzljm","hpziembxjj","tspdcrwbrd","xokormczev","jcuwcrxdio","ijmqziicpg","ouxjsveqca","wqfyybukcp","sybnjkcrqy","scltfoddtf","qztxxahpal","apjxtlqury","lidtztpkar","cjdnyvxpel","niwthedcyf","plrvkwywpu","mchpslzwfm","vyldmddehq","qglufmnfry","uortqssinf","xrwaitnpys","foidmwuzdc","ooojztxwqn","cwnqenssut","qeeepaepse","guffblbunz","bacecevatf","itezkmthgy","hbcpylnuit","kghholjkip","ijakxrsuvz","mhzivtfmki","etjpvacrca","cmvrnkusjc","immsstdxah","qpylmdnwfj","xxysqcjrcs","ldsvvjodsj","cwlkqgshso","gnchrjvzzc","qedekzeedt","fzrzmpqwig","usorrzqjqe","eyqlcudmuv","amgqimiiuq","hmhffadqwa","bpxyddkhfr","pgzqyuibun","utqfrcqbtq","mkyklkdrfr","xwgjteuxzo","fcqyebmlqv","tpegzxnfzj","dkwvbhbcmr","rremdoghwj","aanlmpfehe","dkbglbejof","afmlvayqqd","sdcgcoewyc","jzhksjztxv","mkiirbsdil","hdodicrwvu","coxxambtmt","qohuoodthm","rxgmjckqbv","jfxrieoupd","fdwlbkcvrx","unfqgabdkf","heuazwfntq","nmdcmdidjs","pniamtjaxo","sdnvkxvooc","zclnshudjo","yubntouycs","qfylorgiru","ldguvwzpuu","bdchhjjrkm","nzbyaqyfzu","qzatfjwdni","sqjvtgdzpd","rbszsxjhxb","tzisfirwyh","ymfjqhpzdk","xoobvegggb","ruytuztznz","ieusknjkoa","chbttdgxoi","xfejvbnqib","bjhpwkvpyc","qfmisqkagu","qpxsdfftzb","zcgsjkcser","gslstcwewm","tmoukfxvly","dbgztefvwc","yserwcecfv","waikpktisk","yjcltebphr","mccghwvqac","xxzzxahign","mvillotxud","zfyauvfqbh","zvcteadqvh","dyoryffkuk","nxgptovyci","meyzjxwtnz","wrlhbkttwt","ubhvkmhima","fecksiguko","udnicxrkcv","bjnktficie","vimrcdhlny","luzmrkbuod","uckacspojy","tjulukluyk","bhmslgpeod","buihnyxiwm","xhhkrxtkav","frfhfoelfu","edljlpwcvc","fmjkgulyky","visqasusix","xpkcnxwwbj","bxqyseatub","bsmknvzupf","teqnlnqbfn","kbnwsjbltd","xeswkdeffq","cqmyyaypum","ukxcvbmpii","uozytzegjj","waqrlxtcub","njhlhaqviv","ktdrflrcqd","cbpnhtisuj","tswxgbqlff","glmygpvhun","nbhixjvzfj","divzzzleal","zqqggeleru","hjholwrjeb","vhxmagdfjc","fbrkcuzbhx","dfkolsknmq","dqunofgoai","aghwoekwoq","pjxszbkgmn","fvdoufggal","bigherqoev","nvpcvxmgyz","jjbhrhbypd","ybnqboocnw","ibealdrrev","lpuqyxcbun","qdandzyrlh","ulcmhvraxj","auxtsfahpk","ugnqonsurv","okdlcadvkr","pbzlkpdpql","mykqizxhxb","pkqcukrafd","rzyzurgvec","dbbjitryuy","tqlyfubjpy","ybmlymtzyz","fsoyqtyvll","bjzzkdfgzr","ywepvbllxo","xdxjhqppoi","brxxxyepzr","mjydksqmyw","npebewmbyy","xyfbzzmdof","wvklbqtyvn","whegjxeqtk","bkztjpzmrq","ewsthtbjrt","ardseurdzh","qnfdkabmjs","ytywartowq","fjatvetenq","wnlszaoxpa","vhhgicqxnd","gprhypmpiw","jgjkmpzzfm","wdowzmolct","finthotcit","upmceqjepq","gbrsdomlhb","mdtbsweejz","uwvgfytvgw","wcgwuovtfy","khzuaowtrn","edngubpiyj","eyinqbwtyq","denfcldgtw","svulbfdsei","gvzvthylko","hfbhlaxqoi","hjlmivcfxt","zvciwfovlc","fiiuhdpcar","mozqsoimwr","gruxkjvjue","cczeboorha","hrhmoxuvyq","cgtipwrrpn","pxtpqonuek","rrbyhollma","zlqfvuxfjk","ijwjyqxufd","zfsghopygq","evlvdkjqqg","bztnmktukx","duzyyedjvd","kriljupqls","ghnbbvwxzr","oqdiqzebno","ylmxvfjnef","lymxwcgmvg","fippvlvbeb","jhsuiwqhto","sdexilkvnz","ybgmbjthof","gnfwydxgct","sezydyhdkj","uyrelqzkdz","qqpolljsuv","azajretvon","qtskjtlhit","xwbcasyori","cmddyydphx","qhadrrqtoh","cbiebcjlsl","nolpsequkx","udcryrapth","zmoukbfnpd","xgsixdxdfx","zjvxyctdcx","dmgeicrgpz","cfzaeqhasd","mgswfhrsod","lcegawkmtv","casgahrvyr","iqtlyqiikj","sahcszkhyg","gngidasvae","xywwylkmfc","yymygkkinw","yjycfnxbwc","vucvdickiz","sljswongwi","efbwphdzel","byoymaisrh","ffvdkezyuj","gshrnnkati","wactaxdeqf","myyglkecsw","fkuefpwati","vtstuqbued","yeivgrgept","mpoudpbddi","fgihmzsbrg","akxlgbnaqe","offjwjipvo","rtmwjhkikt"]