I was trying to solve a coding question from leetcode
Given an array of strings words (without duplicates), return all the concatenated words in the given list of words.
A concatenated word is defined as a string that is comprised entirely of at least two shorter words (not necessarily distinct) in the given array.
Example 1:
Input: words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]
Example 2:
Input: words = ["cat","dog","catdog"]
Output: ["catdog"]
This is my code
var findAllConcatenatedWordsInADict = function (words) {
let set = new Set(words)
let res = []
let cache = {}
for (let word of words) {
if (dfs(word)) res.push(word)
}
return res
function dfs(word) {
// if (!word) return true
if (cache[word] !== undefined) return cache[word]
for (let i = 1; i < word.length; i++) {
let prefix = word.substring(0, i)
let suffix = word.substring(i)
if (set.has(prefix)) {
if ( set.has(suffix) || dfs(suffix)) {
cache[word] = true
return true
}
}
}
cache[word] = false
return false
}
};
but its failing for the following testcase -
["abnormals","brick","embezzling","allows","brief","embruted","keyboard","citator","damascenes","periwigged","atonable","antirape","cringing","sunbursts","reinforcers","pylons","vociferates","purview","liposome","reformates","regiments","lickerishnesses","gunners","damascened","gunnery","leasebacks","superboard","pooka","vociferated","censers","listlessnesses","shipwrecking","syncopating","chinkapins","wowsers","zonetimes","haphtaroth","pitiers","scorpions","spookiness","inhabitancy","crunchable","prefabricating","fondled","symbolisms","kumyses","venge","fondler","gabbroid","imblaze","fondles","pinniped","amities","gabbroic","acrylonitriles","vibrant","prefabrication","gangsters","glaucomas","nonmonetary","unconfessed","sagaciousnesses","dicty","zarzuela","twelve","coldcocks","formalising","inflicting","tarnations","allots","lustrings","sonographers","auctioneer","conferments","absurds","suspiration","algological","oversupply","droopier","dolmans","legitimisms","rubaiyat","salines","adjustors","flyless","underpublicized","plugola","usuriously","overmilked","scurrying","disintoxicating","knuckleballers","antiauthoritarianisms","disintoxication","lavishing","technicalities","statisticians","superconductive","derogatively","enclosed","reemploys","strafer","timpanum","cineastes","gangues","retirers","stigmas","strafes","vouchsafes","painterlinesses","bazaar","shinnying","skiver","skives","demisemiquavers","venal","vouchsafed","fortepianos","gypsying","ringbark","tarragons","bluntly","venae","wites","infliction","stimulative","extract","skived","youngberries","encloser","hyperconcentration","bestrode","exasperating","encloses","poltergeist","wited","morceau","vends","emits","mutualizes","hormonal","letterspace","bullpen","propagator","besmooth","withy","castaways","mutualized","vasodilatations","retroversion","vimina","assimilators","hesitaters","assimilatory","dicta","hydrometallurgist","fetology","withe","villosities","ogrisms","fingerprinted","exhumation","flagitiously","strafed","purgings","motorizing","noncompetitor","proselyting","rightisms","wimpishness","stigmal","sabulose","nonadditivities","unknowabilities","cryptorchism","borrowings","tideways","fractions","detachers","biped","emirs","noseguard","droopily","cavettos","luminesce","procrastinated","retirees","penicil","discounting","outdragging","symbolised","paginate","biblicism","reevaluating","biblicist","propagated","therapeutic","impermanences","jeopardised","laminose","microampere","closing","totemisms","venom","symbolises","cobbling","auditoria","cosignatory","jeopardises","combustibles","whosoever","perfunctoriness","kamseen","jabots","implicatively","shadower","anorexias","reevaluation","unconstitutionalities","countermand","immunotherapies","procrastinates","thyroglobulin","mayapple","johnny","apagoge","osmeteria","propagates","astringencies","lymphosarcomas","coshered","jellyfish","hormones","laminous","depositary","disreputabilities","papovavirus","gypsyism","robes","routinizations","oncogeneses","gypsyish","legitimists","trainability","unrooting","trovers","demilitarizations","sargassum","dicot","prostatisms","shadowed","drooping","exasperation","witty","atresias","healthfulnesses","malposed","robed","taximeters","aerily","truckle","defibrillate","disrobe","desirability","slipware","upstair","relentlessly","hyalin","outtrumping","hydrocracking","unravel","quadrangles","proselytize","rattlesnakes","perverted","roble","heartbroken","proselytise","brills","vibrate","configurational","proselytism","stucco","bowfin","spitting","perverter","strangenesses","epiphenomenalism","talkinesses","profiled","preconsonantal","vibrato","upstage","multidisciplinary","codeveloper","outbidden","mattock","tweenies","profiles","rarebit","codeveloped","venin","brisk","leveeing","profiler","paddleboats","hormonic","colonisation","substantialities","oncogenesis","condemnatory","sclereids","ancon","banalities","fractious","sixtyish","ampuls","blunted","brits","britt","groundlessnesses","somewhats","trekking","rightists","contuses","tonometers","employables","sanctify","coalesces","togaed","pasquinaded","blunter","oxalis","dildoe","spiritualized","ampule","robin","dicks","skewers","chillums","contused","pasquinades","scutellated","oxalic","dicky","cornhuskings","ungraciously","wangled","refreshment","salinas","sargassos","toothbrushings","superheats","microfungus","selsyns","norias","vasodilator","atrioventricular","affectionless","defenselessly","eradiating","coalesced","leadless","spiritualizes","wangler","allegers","satyr","wangles","dildos","sleigh","transportabilities","penalises","downsides","cormorants","motels","pervasion","numerally","overnutritions","pummel","rupture","arnattos","penalised","afflict","prison","pores","twiners","tinhorn","multifariousness","photograms","neutral","redivisions","tonality","combings","eliciting","rewrite","macroevolutionary","subjectively","scarcities","trilogies","storksbill","expendable","finalizations","numerological","insistences","pigeonhole","reactant","tirelessness","shmaltzier","noncolors","hubbly","phenacite","deluge","grizzlers","covenants","countercheck","multilayered","coexecutors","fervent","chainwheel","derailleurs","borrowed","odeons","cladist","deliciously","borrower","combines","pored","combiner","photograph","geophysicists","quintuplicating","combined","illimitability","liberal","senates","amyotonias","diazinon","belonging","inoculating","incredulity","restriven","geomancy","saxes","rookeries","weighted","bulkinesses","blackguarded","restrives","transmogrifying","indocility","singletrees","indicational","porks","protohumans","crackers","antifemale","antihunter","davies","asymmetries","strange","weighter","boondock","microwatts","ungenerosity","fellmonger","hypothecation","immunoprecipitate","sparging","amberinas","legislature","crutched","stimulatory","portrayers","prisms","outvoicing","stimulators","boshvarks","hypothecating","inoculation","methinks","bummed","pigpens","confinement","sneezing","ruralisms","ricochet","tallyhos","travoises","porgy","noncollectors","headlessness","engender","neptunium","superminicomputers","halenesses","humdrums","fancifying","morbidly","benzidin","formfitting","roadhouse","presumptuousnesses","crutches","auntliest","motormouths","sultriest","wiriest","farrow","vermilion","hopeless","nonrealistic","bummer","spinosity","strands","motets","porny","cholates","porns","infield","grenadines","porno","birse","microtones","nonpayments","pollinate","birrs","nephrosis","gherkin","rosiest","extremest","soutache","besiegers","birth","bromids","loving","thresholds","thunderstricken","ossicle","dishevel","estival","volleyball","nauseas","advertencies","clupeoid","tonetics","concelebrations","blackboards","bromide","syncretistic","gastreas","hubbub","hygienes","outfeast","meltdown","allopolyploids","renationalization","balaclavas","centerfolds","neutralnesses","amadous","psittacoses","brownshirts","misfaith","porky","ozonise","redear","travestied","fimbria","creditworthinesses","dialling","enamelwares","phoronids","manchineels","reticulocytes","milliohms","allopolyploidy","postisolation","granddaughter","verge","nebenkern","noncertified","peptic","peptid","millstones","intermixed","prohibit","redefy","chisels","superstores","restlessly","crisscrosses","microtonal","semiarid","inspissating","estrous","manner","prizefightings","bevatrons","bronchoscopy","artier","preprocess","profiteroles","travesties","fresheners","clitics","crisscrossed","cokehead","verbs","inoculative","goofball","nephroses","hosannaing","crassly","outroared","oxygens","dickcissel","lapins","presynaptically","stoloniferous","italics","samechs","belittle","microstate","ravigote","rickey","retwist","hygienic","interlarded","intermixes","senator","ruralists","subteen","clumsily","soapberries","overdesign","mercurate","bronchoscope","bioactivities","ricked","puttying","analgesias","lactobacilli","prises","sleeted","smattered","brisks","disenthral","hymenopterous","misinform","miscommunication","redeem","department","hippiest","cosmical","cosmogonic","prised","allude","hypersexualities","sneezier","subtotalling","uncontested","besmirching","inanition","ecdysones","salivas","inspissation","muzzling","teraph","semilethals","picayunes","enterers","midair","shrivels","treading","encamped","revisable","exocytosis","bigamy","smatterer","caresser","caresses","twitchers","bighorns","apparatus","angas","bromine","reechoing","prereleases","analgesics","mannan","mannas","teenagers","incandescence","caressed","yarely","violaters","liberty","carjacker","poussie","lexica","candidacies","zibeline","meeting","pontes","bronchospastic","controllabilities","fennecs","cutinising","protonic","exocytotic","aerobe","norite","iambic","bistros","humming","sizings","comparisons","terais","wildfowl","reflectorizing","seasoning","postpositionally","quinsies","dateline","canvased","multimode","butterscotch","tidinesses","shrivers","trackball","habilitation","deluxe","limousine","splendiferousnesses","trommel","dashiest","positiveness","overblouses","feoffments","grottoes","davits","signeted","emerging","humidors","aquaria","squaring","binoculars","keycards","queenliness","tzarinas","artily","practicum","airmobile","habilitating","manned","subtest","bison","uncongenialities","johannes","withal","hominizing","instroke","frostbitten","pontil","unrighteousnesses","plenitudes","mischance","subtend","eglateres","infractions","immunoregulatory","irrefutability","housewarmings","adjuvant","neutron","postpartum","beauteous","accountable","exaggerates","watertightnesses","correctors","volatilised","ribonucleotides","recrudesce","taboulis","hubcap","exaggerated","proximity","reliabilities","rigorousness","accountably","narghiles","guyed","complaining","mournfulnesses","outguiding","miticide","resolvable","clumsier","demandingly","volatilises","intangiblenesses","reentrants","yarest","doorpost","bisks","weensier","deifical","pozzolanas","agatized","volatile","withed","linums","counterintelligence","afterbirths","ferredoxin","quinela","agatizes","dihedrals","immobilizations","redeny","prostate","withes","cordelling","neophiliacs","wither","hymenopterons","insectivores","tray","coverings","wamble","hammered","peristomial","lipoprotein","charismatics","infant","reiteratively","puisnes","hammerer","hypnotherapy","trad","trap","tarzan","tram","incurably","fugitivenesses","glaciology","hypotenuse","unsilent","reassuring","incurable","ringmaster","mailability","infamy","adenyl","bicameralism","ridglings","bises","impulsiveness","typewrote","gazebos","epigeneses","mentation","ozonide","preconcerts","wambly","summarising","coattests","inanities","benevolences","pegmatite","mediastinum","utilisers","varlets","waterlogged","artist","satisfactions","unswathed","tocology","initiations","infall","paleness","profanities","buskined","damped","lacrimal","performabilities","sloughy","inkstone","consenting","replenishment","sidecar","touraco","acclaimer","sloughs","rebreed","offhanded","starnose","henceforth","bistres","carboyed","henbit","skidway","hessians","yapping","dabblings","bromism","bistred","unswathes","wonderland","grandiose","insanitations","priestlier","conducers","grandioso","facility","defeated","prissy","trey","spastics","assumptions","trek","damnatory","yikes","stegosauruses","pickabacks","redisplays","companioning","peripherally","tret","rolfers","ordaining","comanage","damper","supervirtuosos","encapsulates","petiolules","porch","acclaimed","dampen","tree","blackguardly","tref","flooding","overpersuading","shoptalks","infantilization","fecklessly","vinicultures","annalists","epigenesis","killdeers","marcato","defeater","neurulations","gametophores","guardrooms","infare","kookie","circumstantialities","ruralises","extinguishments","diazines","subtext","dippable","aglimmer","electrically","delved","mucoidal","squarish","illimitablenesses","visaing","ruralised","embowelled","dimethylhydrazines","encapsulated","hiccupped","electrometer","capacitive","fennels","misbalanced","delver","superromantic","delves","biacetyl","meshuga","mezzotints","landslide","misbalances","lifelines","reelected","skinflints","unfulfillable","bromins","homosex","pozzolanic","furrows","jugful","amosite","trashier","flubbers","demobbing","nightscope","pangram","stooged","buttermilks","monsteras","conjurers","dioptric","teiids","trio","trip","wergilds","anent","trim","disbowel","stooges","oxalate","morosities","vermian","dispassionately","dominicker","fossicked","bicolours","holard","levelling","trig","fustiest","population","fossicker","tressures","trapdoor","dupable","ultraclean","adepts","cuittling","furrowy","ultradistances","casuistic","intoxicate","remigrations","handbreadths","photogravure","fingerholds","damply","straggles","populating","kneeled","redeye","straggler","transistorization","skyline","caliper","casuist","reprehend","deforms","relevances","disparity","kneeler","archetypal","princeliest","tribadic","cysticercoid","hydroponically","insulations","pinkeyes","desultory","outprices","calipee","parsimonious","noctules","retakers","astricted","kipped","astigmatism","uppityness","straggled","outpriced","praenomen","millefiori","shunpiking","gudgeon","entelechy","pronouncements","folkmoots","patchoulies","nitrifiers","underwear","chamaephyte","bromize","pouchiest","temporizers","bookstores","monomania","parleyer","swaggers","telneted","nacres","scholar","pancratiums","preeminence","cerites","timpanums","whatshisname","inbounding","nacred","pitifullest","bookings","iambus","prioritizing","vitalisms","solemnnesses","acrotisms","lightered","parchments","wattlebirds","sawed","constrictors","cutesie","gearwheel","jujitsu","symbolized","symbolizer","trow","symbolizes","parleyed","ruralities","sawer","trot","nudenesses","anele","ghoulies","smelted","susurrations","twerps","troy","humannesses","overcures","trod","sketchiness","supercargo","trop","yearlies","incandescents","merchanted","postage","witticism","unchangeability","overcured","arboretums","kentledge","crispened","waistbands","firehall","prearrange","brucine","unchurching","stonecrops","nontreatment","nonreciprocals","saprogenic","waterbird","opprobrium","brucins","attempered","saluters","twiniest","universalisms","underwent","reexporting","peponiums","cocaptains","procrastinations","wadies","madwort","trashing","scintillate","univocal","eupnea","forestalling","paganizing","subaquatic","paresthetic","epileptogenic","pushups","rollicking","pepsin","nonathlete","spittoon","precincts","tallying","guildship","reclassify","unsicker","enlacement","homeopathic","tracksuit","brunette","kneading","impetuses","parenchymata","yarded","within","obsessives","supercivilization","cavalcade","acronic","convertaplanes","biomathematics","rhizobia","maladapted","sauciest","taffetized","prelimit","bowler","adjustive","anear","firefangs","substanceless","riderless","voling","scholia","bowleg","phlebotomists","beveler","bowled","kippen","pipeless","ravishments","arkose","kipper","statoblast","redfin","spinelessly","heehaw","unirradiated","clarinetists","postals","trug","sericulturist","whimpering","homogeneously","beveled","abscessing","canvases","frotteurs","canvaser","carboxyl","methoxychlor","true","isocracy","clarioned","fetologies","laughter","aphrodisiac","proverbed","yippee","dangerous","chickarees","loiterers","effectually","universalists","graptolite","philistine","tombaks","archetypes","acajou","vitalists","lamentedly","yipped","windowsills","ecophysiologies","iceboats","cogenerations","trashily","tribades","noninfective","uninteresting","renowns","skimped","sidearm","yearling","caliphs","gripers","turnhalls","deuteranomalous","abulias","online","bipyramids","misrenders","durian","diallist","twinged","neurosensory","uninsulated","horseraces","fashioner","footboys","kyat","gradational","mistreated","phreatophytic","interperceptual","pulpwood","inveiglers","pentagon","biofouling","stingrays","sympetalous","fashioned","glossolalist","soroches","antimoderns","birks","fibrefills","popsy","savvy","baptismally","kyak","benzanthracenes","kyar","pregnable","splattered","tricotines","tsarisms","twinges","disastrous","pickaroons","unfreedoms","coltishly","entoderms","waylayers","speechlessness","bowmen","oospore","birls","poppy","togged","cypruses","figurativeness","knocked","slewing","mutualists","pooches","interventionism","arbute","newsboys","sukiyaki","interventionist","birle","probands","subseizures","wonderfully","yippie","coappears","poppa","wading","ambitioned","admonition","intellectualization","hedgerows","coercively","scintillant","unambitious","astigmatics","confusional","tubbiest","equabilities","lagoon","ascensions","extolment","fagotings","fetologist","gutlessnesses","pooched","velocimeter","exocytoses","fastback","conforms","standardises","branchless","descriptions","terbic","rebills","terbia","standardised","graveyard","phyllite","adjusting","pudgier","chestnuts","treelike","acromia","veepee","viscously","abstractable","descendible","dilutions","constructor","probangs","reinvests","tombacs","hypostatize","microphotographs","effectivenesses","tenderometer","ambivert","prospectors","tetracyclines","ghoulish","descriers","kinkajou","knocker","microphotography","subcategory","acquests","fecundations","saintly","crasser","bontebok","bounders","paregoric","eyeballing","watchcry","tsar","jukebox","enterotoxins","pinelands","retables","forwarding","irrationalities","rodeo","syncopators","evert","foodlessness","overpowers","backpacker","naturism","tomback","treatabilities","naturist","every","bowman","glaive","staminate","backpacked","introfies","branchlets","taxpayer","radiosensitivities","sourwoods","germinations","emigre","introfied","cichlidae","exogenous","quintessential","jayvees","successionally","stichomythia","totalitarianisms","inconvertibility","during","stichomythic","telecast","ancone","mutualisms","scallop","sidebar","spirometric","rambouillet","lathery","maplike","translatability","nonprogressives","sharpness","leptospires","droughtinesses","metallophones","mirlitons","glaire","lathwork","peduncles","airdate","birch","lathers","capstone","exemplifications","peduncled","glairs","durion","breezinesses","daylighted","syllabicate","misentry","glairy","janizaries","wordiest","phosphorylations","biodynamic","equivocating","venire","wauchting","birds","diets","disinfesting","sheepherding","bonifaces","uncertainly","colistins","comeliness","rapscallions","inarticulately","buoying","event","forefeeling","evens","unmanneredly","dioptral","coupon","headstones","lintol","calicoes","jargonistic","metabolizes","downstream","quantongs","toggle","equivocation","metabolized","butterflyers","transistorising","bonnocks","shuttlecocking","alchemists","thymectomizing","manacling","pudgily","nonplus","storytellers","ruralites","progestin","artificer","diene","fondest","abridgement","vitalises","accelerandos","nonparasitic","artifices","interorgan","allure","nonpartisanships","regrafts","tighteners","amontillado","contacting","explosively","denotations","leptospiral","onrushes","surfperches","uncorrupt","arresting","hymnody","mainmast","oarlike","workstation","disheartened","caraganas","orceins","vitalised","speedings","deashing","lectureship","heretically","lungworms","coffeehouses","postbag","evadible","frequent","sequacities","tenderization","pneumonia","dartboard","pneumonic","switchers","exploiters","slowworm","constructed","bonsai","bloodbath","currently","ambassador","aspheric","chincherinchees","maraschinos","phreatophytes","dioptres","justifiability","nongravitational","archeologists","fernless","mantelshelf","redbug","redbud","gypsydom","stoniness","infirmaries","tsks","kymographies","morphogenesis","pickthank","roadbed","dottles","arcuate","enduro","fonding","lensman","envied","disharmonious","wizes","abridgements","cystoliths","habitualness","capablenesses","wizen","cultural","gigantesque","germinally","pentazocine","coprophilous","artful","heptagon","backlighting","endure","placement","disremembered","hairpins","overclassifies","cultured","slanderously","essence","flagellants","hyperinflations","transnatural","interlinearly","mesenteries","uncertainty","robbed","chivvy","multidrug","lordlier","overclassified","concessionaires","coinventor","unsheathed","envies","envier","dithering","cochairing","barbarity","holdup","jezails","beanbag","cyanohydrins","unsheathes","gamesman","vetch","libretto","unkindness","organogenesis","kyte","exobiology","libretti","solitudinarians","yokemate","salivators","collarets","jazzmen","robber","cleanhanded","aerospace","superscriptions","outsinning","couple","piggish","infrahumans","jazzman","paratactical","quatercentenary","oilcloth","skywriters","embonpoints","zombiisms","contraventions","reddishness","godroon","inhaling","jewfish","inditer","unscrupulousness","vivify","cystoscopic","angakok","interservice","reversions","formularizations","indites","barbarism","foozle","middling","cultures","donnybrooks","blinkards","pastoralists","indited","carnallites","differentiable","misdescribe","pentathletes","toreutic","sanctuaries","bistort","happiness","rostra","patchier","polyhistoric","finniest","bafflements","courageousness","plexiform","transportable","orthopsychiatry","potlatched","dogmatisms","passover","boyhoods","vacillators","chiasmic","sincipital","rhetorically","venins","potlatches","reoxidations","tumescences","cebid","lefter","quirkinesses","venine","buncoed","hussar","reconstitution","cabs","helmeted","enticingly","hypostyle","caca","buncoes","bursitis","connects","saunters","nonplay","slingshots","tapeworm","scorepads","potsy","unzipped","reconstituting","violoncellists","dustpans","nonchalant","breechclout","cystoscopes","sparkplugging","sacerdotally","hydroponics","pseudocholinesterases","resoaked","sleeves","updived","other","cads","corpuscular","weiners","sleeved","selectionists","venial","cadi","oblations","constipations","updives","reptilium","silkolines","nonsteroids","allosterically","phaseal","protagonist","mofette","shackles","spectrums","shackler","verdicts","detaching","proofer","inhabiting","pseudomonades","postcolleges","posteriorly","pigging","tsarists","unawarenesses","doomsdayer","binnacle","cade","proofed","xanthene","threadworm","sociopath","piggins","fertilities","motortrucks","prevaricators","selfhood","uraninites","ergodicity","alleging","pastoralisms","apoenzyme","impairers","scissor","spiffed","paraffining","rabidnesses","resounded","sisals","cage","infeoffs","passacaglias","burglary","commissions","khazens","punctuating","morphogeneses","dodderers","counterchanged","complement","courseware","soothingnesses","besoothes","clerkdoms","lawyerlike","waylaying","couped","bitsy","applicable","lintel","outdistance","shackled","sainted","transmissivity","caff","besoothed","tunesmith","factorage","cafe","sprattle","stoutnesses","linter","coupes","infract","smaragdine","ladyship","legrooms","incomprehensiblenesses","overmelting","pyrexic","pyrexia","bassinet","inflicters","overjoyed","bitty","potty","leones","simplex","spittles","endoderms","cudbears","apishness","tridimensional","jujutsus","backfitting","potto","simpler","witing","simples","underletting","weakness","sonographies","overingenious","caid","kerogen","bitts","dogmatists","remonstrators","switchable","isogenies","plagioclases","counterchanges","unicameral","redcap","organogeneses","bravoing","defacement","burglars","beetroot","cutwater","gamesmen","robbin","telestics","prescreenings","alkahestic","negligences","compilation","tenailles","garboard","punctuation","infight","cutins","cagy","uredospores","emblemed","allowably","farted","prosecution","privet","quenelles","cofounding","flummery","phyllotaxies","allowable","circumscissile","narrowcasting","hightails","naught","cake","broil","reedmen","nominalisms","lightning","broke","intravenouses","temporizing","quicksets","stuffs","enterochromaffin","cain","andantes","coexist","upthrusts","verandas","workless","duchess","antileprosy","choices","jawbonings","doorplate","choicer","microwaves","calx","slathering","splendrous","algebra","kokanees","calo","photoproducts","microwaved","galoshes","zincifying","flamming","aeons","protopod","came","introverts","masterfulness","oculist","overplayed","chives","regionals","allosauruses","describer","caky","zappiest","galoshed","hoddins","matting","geologists","holder","brome","nonmoney","describes","holden","call","linsey","calm","nationalizers","trapballs","calk","watchdog","calf","wappenschawings","unrelievedly","undeviatingly","mattins","blockbusting","psittacotic","biostatisticians","reportedly","mythicize","cant","exchequer","cans","bootlace","mother","reedman","coinvented","quaggiest","depredate","lungans","intransigently","transfect","cams","consecrate","camp","goggling","cane","foregathering","foveolets","archosaur","cuties","xanthein","irresistiblenesses","verandah","casuistry","attrite","caps","wildcatting","mesophyllous","beatifically","nankeens","syncytia","crying","relighted","proestrus","fractionations","breechcloth","assailing","sensing","polychromatophilic","ruminatively","hypochondriacal","polychromatophilia","outwearing","fructose","newborn","palynological","capo","phagocytotic","presignify","caph","aquatic","clostridial","aliterate","cape","smaragdite","casa","reattempting","russeting","usage","lomeins","votarists","cheapness","negotiable","chansonniers","cart","monitored","tapetal","deforce","cast","crosswind","deporting","haddest","vestibule","empalers","broad","cask","educt","squirmers","autochthonous","ricins","cash","case","rivalling","andromeda","dolmades","carb","dolefuller","rostrally","educe","noncomputer","anorthosites","reveled","ricing","peroxisome","ascarids","polydispersity","smelter","nonintercourses","carr","effigy","cars","beylic","carp","carn","carl","diazepams","patchily","refolding","cark","reveler","beylik","annunciation","progressional","card","care","annunciating","loitering","bailiffships","corelating","intravenously","enjoiners","preconceiving","redbaits","hypotensives","editorializers","grapline","reoperated","procephalic","decomposes","persnicketinesses","transfers","decomposer","desalinating","nonhomologous","burthen","caul","collisionally","brock","insubordinate","graplins","rearmaments","cate","lithographs","helpings","impartation","decomposed","plessor","cotransduce","heterologous","usurpation","intoxicant","lithography","reinspired","nonabrasive","nalorphines","isomorphs","facemask","infestation","wretchedest","cats","nontitle","misregistering","reoperates","decrials","tautonym","repolls","jubilance","masturbations","jinglers","neonatologists","vests","photometers","cavy","endued","fustians","smitten","jarsful","saluting","caws","chiasmal","chrysalids","northwards","emailing","morbific","microbrew","shrewdly","inwrap","mealiest","chiasmas","described","kneeling","rawhide","rogue","cave","shoebill","dracaena","rewires","churlishnesses","desalination","shatter","cocultivation","postdive","rewired","unraveled","varisized","bacteriostat","elbowing","immunofluorescences","gogglier","endozoic","crosswise","degaussing","endues","vesta","gangrel","anatomising","bumkin","bulliest","indefectible","reptilian","anorthositic","patching","increate","photodetectors","stuffy","cays","absorptions","consonants","strakes","matrices","prosecuting","coplanarity","indefectibly","bipinnate","credulousness","barbarize","paleographical","prepotently","radiotelemetry","orthogonalities","flagitiousnesses","fruitfuller","coniine","increase","cocultivating","disproving","squinnying","fervencies","treasurable","backwraps","dibbukim","epi"]
Any Help/hint would be appreciated
Objects have properties like constructor, toString, etc. that can make it seem like those values have already been cached. Instead, you could use a Map (or Object.create(null)).
var findAllConcatenatedWordsInADict = function (words) {
let set = new Set(words)
let res = []
let cache = new Map;
for (let word of words) {
if (dfs(word)) res.push(word)
}
return res
function dfs(word) {
if (cache.has(word)) return cache.get(word);
for (let i = 1; i < word.length; i++) {
let prefix = word.substring(0, i)
let suffix = word.substring(i)
if (set.has(prefix)) {
if ( set.has(suffix) || dfs(suffix)) {
cache.set(word, true);
return true
}
}
}
cache.set(word, false);
return false
}
};