Word Ladder II

[xqian]

http://leetcode.com/onlinejudge#question_126
http://discuss.leetcode.com/questions/1051/word-ladder-ii

[xqian]

Run Status: Accepted!
Program Runtime: 8 milli secs
Progress: 13/13 test cases passed.
input output expected
"a", "c", ["a","b","c"] [["a","c"]] [["a","c"]]

"hot", "dog", ["hot","dog"] [] []

"hot", "dog", ["hot","dog","dot"] [["hot","dot","dog"]] [["hot","dot","dog"]]

"hot", "dot", ["hot","dot","dog"] [["hot","dot"]] [["hot","dot"]]

"hot", "dog", ["hot","cog","dog","tot","hog","hop","pot","dot"] [["hot","hog","dog"],["hot","dot","dog"]] [["hot","hog","dog"],["hot","dot","dog"]]

"hot", "dog", ["hot","dog","cog","pot","dot"] [["hot","dot","dog"]] [["hot","dot","dog"]]

"hit", "cog", ["hot","cog","dot","dog","hit","lot","log"] [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]] [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]

"hit", "cog", ["hot","hit","cog","dot","dog"] [["hit","hot","dot","dog","cog"]] [["hit","hot","dot","dog","cog"]]

"red", "tax", ["ted","tex","red","tax","tad","den","rex","pee"] [["red","ted","tad","tax"],["red","ted","tex","tax"],["red","rex","tex","tax"]] [["red","ted","tad","tax"],["red","ted","tex","tax"],["red","rex","tex","tax"]]

"lost", "cost", ["most","fist","lost","cost","fish"] [["lost","cost"]] [["lost","cost"]]

"lost", "miss", ["most","mist","miss","lost","fist","fish"] [["lost","most","mist","miss"]] [["lost","most","mist","miss"]]

"leet", "code", ["lest","leet","lose","code","lode","robe","lost"] [["leet","lest","lost","lose","lode","code"]] [["leet","lest","lost","lose","lode","code"]]

"talk", "tail", ["talk","tons","fall","tail","gale","hall","negs"] [] []

Run Status: Time Limit Exceeded

Last executed input
"raining", "cellini", ["heaping","conning","nipping","wadding","pulling","lunging","figging","donning","jamming","coating","foaling","ousting","dowsing","busting","penning","lapping","yanking","sapping","tasking","rigging","ranking","larking","farming","dunging","nutting","gouging","barfing","fasting","belting","boiling","boating","dipping","kilning","barking","furling","calving","veiling","decking","ricking","salting","lucking","sending","taiping","marking","martina","warping","bulking","seaming","topping","larding","jilting","besting","weeding","nesting","baiting","jibbing","pelting","bushing","garbing","banting","keeping","venting","rapping","binning","mulling","smiting","hatting","tapping","writing","footing","carding","ratting","bagging","sitting","dousing","pinking","testing","passing","gelling","gassing","ranging","hefting","vamping","wetting","paining","rolling","sinking","yakking","shaking","nabbing","licking","sparing","hamming","celling","halving","matting","landing","kooking","pinning","hagging","narking","soaping","winding","dealing","earring","cunning","moating","skiting","jutting","fueling","hooping","guiling","mapping","hailing","gutting","firming","bunting","mealing","rending","jobbing","pauling","foiling","peeking","rollins","lansing","felling","whiting","vealing","resting","saltine","earning","purging","mullins","pausing","colling","banning","wasting","sealing","gigging","scaring","pocking","massing","curring","storing","dinging","handing","pitting","faining","cupping","staring","riffing","gowning","hipping","vanning","darting","maiming","damping","deaning","bellini","kipling","marting","hawking","fending","kicking","beading","curving","wending","yelling","foaming","rifting","surging","gaining","stoking","panging","winking","nursing","oinking","looking","tolling","bailing","tanking","hacking","warming","cooping","wanting","rotting","kinking","bugging","purling","wincing","joining","belling","wilting","tensing","fellini","wilding","binding","bugling","sagging","nagging","binging","tatting","cellini","silting","belying","ripping","crating","slaking","killing","hurting","running","harming","banding","rinking","staying","touting","hasting","melting","nibbing","talking","ganging","bonging","rilling","damning","pooling","porting","sinning","collins","barbing","bunking","smiling","hanging","tending","bulging","ginning","coiling","lolling","molting","letting","mending","hinging","gunning","melding","dilling","shaving","harping","basting","cobbing","carting","leading","styling","fowling","goading","yowling","zipping","wagging","gaoling","panning","valving","peeling","titling","sailing","harding","parring","haloing","quiting","punting","reeling","batting","signing","pegging","bogging","mashing","rankine","seeding","sassing","wafting","winging","framing","rooting","longing","sabling","bulbing","whiling","balking","canting","dashing","dueling","renting","booting","whaling","vatting","veining","fencing","yucking","slaving","welling","sunning","lulling","purring","dawning","sensing","meaning","wording","hogging","parsing","falling","yelping","dinning","vetting","hulling","reading","lapsing","tooling","hoaxing","roiling","forming","ramming","gelding","felting","popping","walling","costing","welding","washing","filling","lasting","couping","cabling","getting","winning","carping","martins","bilking","burning","jelling","sicking","tinting","ceiling","totting","balding","kenning","tinging","hugging","westing","burring","pasting","pecking","parking","slaying","pigging","heating","manning","bucking","bussing","gagging","goaling","rowling","netting","funking","pitying","jarring","tasting","putting","beating","funding","mauling","balling","molding","shining","perkins","dialing","panting","looping","welting","relying","dulling","dumping","tanning","warring","gatling","staging","finding","farting","petting","picking","swaying","toiling","jambing","bawling","minting","wedding","hulking","keeling","nanking","railing","heading","cutting","gosling","vesting","sighing","mucking","copping","polling","raising","fooling","hooting","titting","calming","seating","rifling","soiling","dubbing","jesting","posting","sacking","corking","yipping","lathing","bopping","setting","coaxing","poshing","fawning","heeling","warning","napping","vending","mooting","hurling","supping","nanjing","pipping","tagging","mopping","souping","palming","gulling","kirking","gilding","docking","wefting","dusting","sharing","darling","bowling","lauding","bidding","hopping","honking","hunting","pepping","busying","damming","patting","hitting","gusting","jigging","gabbing","hosting","sidling","telling","rusting","daubing","reining","memling","healing","gashing","betting","lilting","hashing","salving","firring","gabling","ducking","waiving","skating","worming","waiting","burying","booking","corning","suiting","hooking","gonging","listing","hulaing","sulking","digging","fouling","zincing","cocking","packing","scaling","pooping","zinging","banging","bolling","punning","palling","sipping","bunging","minding","choking","yapping","nicking","warding","gorging","canning","culling","lending","spaying","lashing","pupping","fanning","banking","pinging","roaming","sopping","fonding","searing","fucking","rooking","tooting","raining","billing","pulsing","curbing","cashing","calking","harking","tarring","tacking","whining","tarting","pauline","rasping","howling","helling","curling","pucking","hauling","coaling","lopping","mailing","wailing","lugging","ticking","staving","snaking","selling","masking","jabbing","mewling","heaving","soaring","fagging","cording","begging","ridging","jetting","backing","dotting","lacking","parting","jotting","dunning","tinning","stiling","stating","zapping","hearing","fitting","barging","galling","wigging","feeding","tenting","looting","cabbing","cursing","dunking","dabbing","ragging","bedding","witting","pouting","burping","slating","tamping","basking","failing","papping","narcing","lancing","furlong","tabling","dolling","tailing","pawning","collies","lamming","coifing","bolting","sucking","rafting","morning","ranting","tabbing","rinding","bandung","bashing","bending","ducting","casting","camping","flaming","hinting","sanding","carving","lagging","helping","keening","jolting","temping","junking","manging","dimming","ringing","tipping","spiking","malling","pursing","soaking","willing","fulling","causing","jacking","furring","singing","halting","tucking","ruining","denting","calling","barring","fopping","yawning","tilling","nilling","downing","cooling","martini","budging","lapwing","mincing","rinsing","cowling","marring","coining","sibling","potting","tauting","bulling","lurking","sorting","poohing","bathing","spicing","nailing","spiting","racking","lusting","rutting","gulping","tilting","pairing","peaking","capping","gobbing","finking"]

[tj2013]

so your also could not pass large set. I will profile it.

On Tue, Jun 4, 2013 at 2:36 AM, Xin Qian notifications@github.com wrote:

Run Status: Accepted!
Program Runtime: 8 milli secs
Progress: 13/13 test cases passed.
input output expected

"a", "c", ["a","b","c"] [["a","c"]] [["a","c"]]

"hot", "dog", ["hot","dog"] [] []

"hot", "dog", ["hot","dog","dot"] [["hot","dot","dog"]]
[["hot","dot","dog"]]

"hot", "dot", ["hot","dot","dog"] [["hot","dot"]] [["hot","dot"]]

"hot", "dog", ["hot","cog","dog","tot","hog","hop","pot","dot"]
[["hot","hog","dog"],["hot","dot","dog"]]
[["hot","hog","dog"],["hot","dot","dog"]]

"hot", "dog", ["hot","dog","cog","pot","dot"] [["hot","dot","dog"]]
[["hot","dot","dog"]]

"hit", "cog", ["hot","cog","dot","dog","hit","lot","log"]
[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]

"hit", "cog", ["hot","hit","cog","dot","dog"]
[["hit","hot","dot","dog","cog"]] [["hit","hot","dot","dog","cog"]]

"red", "tax", ["ted","tex","red","tax","tad","den","rex","pee"]
[["red","ted","tad","tax"],["red","ted","tex","tax"],["red","rex","tex","tax"]]
[["red","ted","tad","tax"],["red","ted","tex","tax"],["red","rex","tex","tax"]]

"lost", "cost", ["most","fist","lost","cost","fish"] [["lost","cost"]]
[["lost","cost"]]

"lost", "miss", ["most","mist","miss","lost","fist","fish"]
[["lost","most","mist","miss"]] [["lost","most","mist","miss"]]

"leet", "code", ["lest","leet","lose","code","lode","robe","lost"]
[["leet","lest","lost","lose","lode","code"]]
[["leet","lest","lost","lose","lode","code"]]

"talk", "tail", ["talk","tons","fall","tail","gale","hall","negs"] [] []

Run Status: Time Limit Exceeded

Last executed input
"raining", "cellini",
["heaping","conning","nipping","wadding","pulling","lunging","figging","donning","jamming","coating","foaling","ousting","dowsing","busting","penning","lapping","yanking","sapping","tasking","rigging","ranking","larking","farming","dunging","nutting","gouging","barfing","fasting","belting","boiling","boating","dipping","kilning","barking","furling","calving","veiling","decking","ricking","salting","lucking","sending","taiping","marking","martina","warping","bulking","seaming","topping","larding","jilting","besting","weeding","nesting","baiting","jibbing","pelting","bushing","garbing","banting","keeping","venting","rapping","binning","mulling","smiting","hatting","tapping","writing","footing","carding","ratting","bagging","sitting","dousing","pinking","testing","passing","gelling","gassing","ranging","hefting","vamping","wetting","paining","rolling","sinking","yakking","shaking","nabbing","licking","sparing","hamming","celling","halving","matting","landin
g","kooking","pinning","hagging","narking","soaping","winding","dealing","earring","cunning","moating","skiting","jutting","fueling","hooping","guiling","mapping","hailing","gutting","firming","bunting","mealing","rending","jobbing","pauling","foiling","peeking","rollins","lansing","felling","whiting","vealing","resting","saltine","earning","purging","mullins","pausing","colling","banning","wasting","sealing","gigging","scaring","pocking","massing","curring","storing","dinging","handing","pitting","faining","cupping","staring","riffing","gowning","hipping","vanning","darting","maiming","damping","deaning","bellini","kipling","marting","hawking","fending","kicking","beading","curving","wending","yelling","foaming","rifting","surging","gaining","stoking","panging","winking","nursing","oinking","looking","tolling","bailing","tanking","hacking","warming","cooping","wanting","rotting","kinking","bugging","purling","wincing","joining","belling","wilting","tensing","fellini","wildi
ng","binding","bugling","sagging","nagging","binging","tatting","cellini","silting","belying","ripping","crating","slaking","killing","hurting","running","harming","banding","rinking","staying","touting","hasting","melting","nibbing","talking","ganging","bonging","rilling","damning","pooling","porting","sinning","collins","barbing","bunking","smiling","hanging","tending","bulging","ginning","coiling","lolling","molting","letting","mending","hinging","gunning","melding","dilling","shaving","harping","basting","cobbing","carting","leading","styling","fowling","goading","yowling","zipping","wagging","gaoling","panning","valving","peeling","titling","sailing","harding","parring","haloing","quiting","punting","reeling","batting","signing","pegging","bogging","mashing","rankine","seeding","sassing","wafting","winging","framing","rooting","longing","sabling","bulbing","whiling","balking","canting","dashing","dueling","renting","booting","whaling","vatting","veining","fencing","yuck
ing","slaving","welling","sunning","lulling","purring","dawning","sensing","meaning","wording","hogging","parsing","falling","yelping","dinning","vetting","hulling","reading","lapsing","tooling","hoaxing","roiling","forming","ramming","gelding","felting","popping","walling","costing","welding","washing","filling","lasting","couping","cabling","getting","winning","carping","martins","bilking","burning","jelling","sicking","tinting","ceiling","totting","balding","kenning","tinging","hugging","westing","burring","pasting","pecking","parking","slaying","pigging","heating","manning","bucking","bussing","gagging","goaling","rowling","netting","funking","pitying","jarring","tasting","putting","beating","funding","mauling","balling","molding","shining","perkins","dialing","panting","looping","welting","relying","dulling","dumping","tanning","warring","gatling","staging","finding","farting","petting","picking","swaying","toiling","jambing","bawling","minting","wedding","hulking","kee
ling","nanking","railing","heading","cutting","gosling","vesting","sighing","mucking","copping","polling","raising","fooling","hooting","titting","calming","seating","rifling","soiling","dubbing","jesting","posting","sacking","corking","yipping","lathing","bopping","setting","coaxing","poshing","fawning","heeling","warning","napping","vending","mooting","hurling","supping","nanjing","pipping","tagging","mopping","souping","palming","gulling","kirking","gilding","docking","wefting","dusting","sharing","darling","bowling","lauding","bidding","hopping","honking","hunting","pepping","busying","damming","patting","hitting","gusting","jigging","gabbing","hosting","sidling","telling","rusting","daubing","reining","memling","healing","gashing","betting","lilting","hashing","salving","firring","gabling","ducking","waiving","skating","worming","waiting","burying","booking","corning","suiting","hooking","gonging","listing","hulaing","sulking","digging","fouling","zincing","cocking","pa
cking","scaling","pooping","zinging","banging","bolling","punning","palling","sipping","bunging","minding","choking","yapping","nicking","warding","gorging","canning","culling","lending","spaying","lashing","pupping","fanning","banking","pinging","roaming","sopping","fonding","searing","fucking","rooking","tooting","raining","billing","pulsing","curbing","cashing","calking","harking","tarring","tacking","whining","tarting","pauline","rasping","howling","helling","curling","pucking","hauling","coaling","lopping","mailing","wailing","lugging","ticking","staving","snaking","selling","masking","jabbing","mewling","heaving","soaring","fagging","cording","begging","ridging","jetting","backing","dotting","lacking","parting","jotting","dunning","tinning","stiling","stating","zapping","hearing","fitting","barging","galling","wigging","feeding","tenting","looting","cabbing","cursing","dunking","dabbing","ragging","bedding","witting","pouting","burping","slating","tamping","basking","f
ailing","papping","narcing","lancing","furlong","tabling","dolling","tailing","pawning","collies","lamming","coifing","bolting","sucking","rafting","morning","ranting","tabbing","rinding","bandung","bashing","bending","ducting","casting","camping","flaming","hinting","sanding","carving","lagging","helping","keening","jolting","temping","junking","manging","dimming","ringing","tipping","spiking","malling","pursing","soaking","willing","fulling","causing","jacking","furring","singing","halting","tucking","ruining","denting","calling","barring","fopping","yawning","tilling","nilling","downing","cooling","martini","budging","lapwing","mincing","rinsing","cowling","marring","coining","sibling","potting","tauting","bulling","lurking","sorting","poohing","bathing","spicing","nailing","spiting","racking","lusting","rutting","gulping","tilting","pairing","peaking","capping","gobbing","finking"]

�
Reply to this email directly or view it on GitHubhttps://github.com//issues/10#issuecomment-18898612
.

[xqian]

Yes.

How can we improve time complexity?

On Tuesday, June 4, 2013, tj2013 wrote:

so your also could not pass large set. I will profile it.

On Tue, Jun 4, 2013 at 2:36 AM, Xin Qian <notifications@github.com<javascript:_e({}, 'cvml', 'notifications@github.com');>>
wrote:

Run Status: Accepted!
Program Runtime: 8 milli secs
Progress: 13/13 test cases passed.
input output expected

"a", "c", ["a","b","c"] [["a","c"]] [["a","c"]]

"hot", "dog", ["hot","dog"] [] []

"hot", "dog", ["hot","dog","dot"] [["hot","dot","dog"]]
[["hot","dot","dog"]]

"hot", "dot", ["hot","dot","dog"] [["hot","dot"]] [["hot","dot"]]

"hot", "dog", ["hot","cog","dog","tot","hog","hop","pot","dot"]
[["hot","hog","dog"],["hot","dot","dog"]]
[["hot","hog","dog"],["hot","dot","dog"]]

"hot", "dog", ["hot","dog","cog","pot","dot"] [["hot","dot","dog"]]
[["hot","dot","dog"]]

"hit", "cog", ["hot","cog","dot","dog","hit","lot","log"]
[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]

"hit", "cog", ["hot","hit","cog","dot","dog"]
[["hit","hot","dot","dog","cog"]] [["hit","hot","dot","dog","cog"]]

"red", "tax", ["ted","tex","red","tax","tad","den","rex","pee"]

[["red","ted","tad","tax"],["red","ted","tex","tax"],["red","rex","tex","tax"]]

[["red","ted","tad","tax"],["red","ted","tex","tax"],["red","rex","tex","tax"]]

"lost", "cost", ["most","fist","lost","cost","fish"] [["lost","cost"]]
[["lost","cost"]]

"lost", "miss", ["most","mist","miss","lost","fist","fish"]
[["lost","most","mist","miss"]] [["lost","most","mist","miss"]]

"leet", "code", ["lest","leet","lose","code","lode","robe","lost"]
[["leet","lest","lost","lose","lode","code"]]
[["leet","lest","lost","lose","lode","code"]]

"talk", "tail", ["talk","tons","fall","tail","gale","hall","negs"] [] []

Run Status: Time Limit Exceeded

Last executed input
"raining", "cellini",

["heaping","conning","nipping","wadding","pulling","lunging","figging","donning","jamming","coating","foaling","ousting","dowsing","busting","penning","lapping","yanking","sapping","tasking","rigging","ranking","larking","farming","dunging","nutting","gouging","barfing","fasting","belting","boiling","boating","dipping","kilning","barking","furling","calving","veiling","decking","ricking","salting","lucking","sending","taiping","marking","martina","warping","bulking","seaming","topping","larding","jilting","besting","weeding","nesting","baiting","jibbing","pelting","bushing","garbing","banting","keeping","venting","rapping","binning","mulling","smiting","hatting","tapping","writing","footing","carding","ratting","bagging","sitting","dousing","pinking","testing","passing","gelling","gassing","ranging","hefting","vamping","wetting","paining","rolling","sinking","yakking","shaking","nabbing","licking","sparing","hamming","celling","halving","matting","landin

g","kooking","pinning","hagging","narking","soaping","winding","dealing","earring","cunning","moating","skiting","jutting","fueling","hooping","guiling","mapping","hailing","gutting","firming","bunting","mealing","rending","jobbing","pauling","foiling","peeking","rollins","lansing","felling","whiting","vealing","resting","saltine","earning","purging","mullins","pausing","colling","banning","wasting","sealing","gigging","scaring","pocking","massing","curring","storing","dinging","handing","pitting","faining","cupping","staring","riffing","gowning","hipping","vanning","darting","maiming","damping","deaning","bellini","kipling","marting","hawking","fending","kicking","beading","curving","wending","yelling","foaming","rifting","surging","gaining","stoking","panging","winking","nursing","oinking","looking","tolling","bailing","tanking","hacking","warming","cooping","wanting","rotting","kinking","bugging","purling","wincing","joining","belling","wilting","tensing","fellini","wildi

ng","binding","bugling","sagging","nagging","binging","tatting","cellini","silting","belying","ripping","crating","slaking","killing","hurting","running","harming","banding","rinking","staying","touting","hasting","melting","nibbing","talking","ganging","bonging","rilling","damning","pooling","porting","sinning","collins","barbing","bunking","smiling","hanging","tending","bulging","ginning","coiling","lolling","molting","letting","mending","hinging","gunning","melding","dilling","shaving","harping","basting","cobbing","carting","leading","styling","fowling","goading","yowling","zipping","wagging","gaoling","panning","valving","peeling","titling","sailing","harding","parring","haloing","quiting","punting","reeling","batting","signing","pegging","bogging","mashing","rankine","seeding","sassing","wafting","winging","framing","rooting","longing","sabling","bulbing","whiling","balking","canting","dashing","dueling","renting","booting","whaling","vatting","veining","fencing","yuck

ing","slaving","welling","sunning","lulling","purring","dawning","sensing","meaning","wording","hogging","parsing","falling","yelping","dinning","vetting","hulling","reading","lapsing","tooling","hoaxing","roiling","forming","ramming","gelding","felting","popping","walling","costing","welding","washing","filling","lasting","couping","cabling","getting","winning","carping","martins","bilking","burning","jelling","sicking","tinting","ceiling","totting","balding","kenning","tinging","hugging","westing","burring","pasting","pecking","parking","slaying","pigging","heating","manning","bucking","bussing","gagging","goaling","rowling","netting","funking","pitying","jarring","tasting","putting","beating","funding","mauling","balling","molding","shining","perkins","dialing","panting","looping","welting","relying","dulling","dumping","tanning","warring","gatling","staging","finding","farting","petting","picking","swaying","toiling","jambing","bawling","minting","wedding","hulking","kee

ling","nanking","railing","heading","cutting","gosling","vesting","sighing","mucking","copping","polling","raising","fooling","hooting","titting","calming","seating","rifling","soiling","dubbing","jesting","posting","sacking","corking","yipping","lathing","bopping","setting","coaxing","poshing","fawning","heeling","warning","napping","vending","mooting","hurling","supping","nanjing","pipping","tagging","mopping","souping","palming","gulling","kirking","gilding","docking","wefting","dusting","sharing","darling","bowling","lauding","bidding","hopping","honking","hunting","pepping","busying","damming","patting","hitting","gusting","jigging","gabbing","hosting","sidling","telling","rusting","daubing","reining","memling","healing","gashing","betting","lilting","hashing","salving","firring","gabling","ducking","waiving","skating","worming","waiting","burying","booking","corning","suiting","hooking","gonging","listing","hulaing","sulking","digging","fouling","zincing","cocking","pa

cking","scaling","pooping","zinging","banging","bolling","punning","palling","sipping","bunging","minding","choking","yapping","nicking","warding","gorging","canning","culling","lending","spaying","lashing","pupping","fanning","banking","pinging","roaming","sopping","fonding","searing","fucking","rooking","tooting","raining","billing","pulsing","curbing","cashing","calking","harking","tarring","tacking","whining","tarting","pauline","rasping","howling","helling","curling","pucking","hauling","coaling","lopping","mailing","wailing","lugging","ticking","staving","snaking","selling","masking","jabbing","mewling","heaving","soaring","fagging","cording","begging","ridging","jetting","backing","dotting","lacking","parting","jotting","dunning","tinning","stiling","stating","zapping","hearing","fitting","barging","galling","wigging","feeding","tenting","looting","cabbing","cursing","dunking","dabbing","ragging","bedding","witting","pouting","burping","slating","tamping","basking","f

ailing","papping","narcing","lancing","furlong","tabling","dolling","tailing","pawning","collies","lamming","coifing","bolting","sucking","rafting","morning","ranting","tabbing","rinding","bandung","bashing","bending","ducting","casting","camping","flaming","hinting","sanding","carving","lagging","helping","keening","jolting","temping","junking","manging","dimming","ringing","tipping","spiking","malling","pursing","soaking","willing","fulling","causing","jacking","furring","singing","halting","tucking","ruining","denting","calling","barring","fopping","yawning","tilling","nilling","downing","cooling","martini","budging","lapwing","mincing","rinsing","cowling","marring","coining","sibling","potting","tauting","bulling","lurking","sorting","poohing","bathing","spicing","nailing","spiting","racking","lusting","rutting","gulping","tilting","pairing","peaking","capping","gobbing","finking"]

�
Reply to this email directly or view it on GitHub<
https://github.com/xqian/cpp_projects/issues/10#issuecomment-18898612>
.

�
Reply to this email directly or view it on GitHubhttps://github.com//issues/10#issuecomment-18921705
.

QIAN, Xin (xqian@unh.edu chianshin@gmail.com)
http://www.sciencenet.cn/u/chianshin/

[tj2013]

I found the dominantly costly part is to calculate neighbors. so I made two
change

1. instead of compare each pair of strings, cost N * N/2 * L, L is the
   length of string
   for each string, I check all strings who have one character different, to
   see if they exist. So the cost is
   for each string, 26 * L * L (second L is to query a hashtable of strings)
   total cost is N * 26 * L * L which is much better considering the N and L
   of the test cases.

2. instead of calculate all neighbors, I only do it when needed

I think 1) is the major improvement.

On Tue, Jun 4, 2013 at 9:37 AM, Xin Qian notifications@github.com wrote:

Yes.

How can we improve time complexity?

On Tuesday, June 4, 2013, tj2013 wrote:

so your also could not pass large set. I will profile it.

On Tue, Jun 4, 2013 at 2:36 AM, Xin Qian <notifications@github.com<javascript:_e({},
'cvml', 'notifications@github.com');>>
wrote:

Run Status: Accepted!
Program Runtime: 8 milli secs
Progress: 13/13 test cases passed.
input output expected

"a", "c", ["a","b","c"] [["a","c"]] [["a","c"]]

"hot", "dog", ["hot","dog"] [] []

"hot", "dog", ["hot","dog","dot"] [["hot","dot","dog"]]
[["hot","dot","dog"]]

"hot", "dot", ["hot","dot","dog"] [["hot","dot"]] [["hot","dot"]]

"hot", "dog", ["hot","cog","dog","tot","hog","hop","pot","dot"]
[["hot","hog","dog"],["hot","dot","dog"]]
[["hot","hog","dog"],["hot","dot","dog"]]

"hot", "dog", ["hot","dog","cog","pot","dot"] [["hot","dot","dog"]]
[["hot","dot","dog"]]

"hit", "cog", ["hot","cog","dot","dog","hit","lot","log"]
[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]

"hit", "cog", ["hot","hit","cog","dot","dog"]
[["hit","hot","dot","dog","cog"]] [["hit","hot","dot","dog","cog"]]

"red", "tax", ["ted","tex","red","tax","tad","den","rex","pee"]

[["red","ted","tad","tax"],["red","ted","tex","tax"],["red","rex","tex","tax"]]

[["red","ted","tad","tax"],["red","ted","tex","tax"],["red","rex","tex","tax"]]

"lost", "cost", ["most","fist","lost","cost","fish"] [["lost","cost"]]
[["lost","cost"]]

"lost", "miss", ["most","mist","miss","lost","fist","fish"]
[["lost","most","mist","miss"]] [["lost","most","mist","miss"]]

"leet", "code", ["lest","leet","lose","code","lode","robe","lost"]
[["leet","lest","lost","lose","lode","code"]]
[["leet","lest","lost","lose","lode","code"]]

"talk", "tail", ["talk","tons","fall","tail","gale","hall","negs"] []
[]

Run Status: Time Limit Exceeded

Last executed input
"raining", "cellini",

["heaping","conning","nipping","wadding","pulling","lunging","figging","donning","jamming","coating","foaling","ousting","dowsing","busting","penning","lapping","yanking","sapping","tasking","rigging","ranking","larking","farming","dunging","nutting","gouging","barfing","fasting","belting","boiling","boating","dipping","kilning","barking","furling","calving","veiling","decking","ricking","salting","lucking","sending","taiping","marking","martina","warping","bulking","seaming","topping","larding","jilting","besting","weeding","nesting","baiting","jibbing","pelting","bushing","garbing","banting","keeping","venting","rapping","binning","mulling","smiting","hatting","tapping","writing","footing","carding","ratting","bagging","sitting","dousing","pinking","testing","passing","gelling","gassing","ranging","hefting","vamping","wetting","paining","rolling","sinking","yakking","shaking","nabbing","licking","sparing","hamming","celling","halving","matting","landin

g","kooking","pinning","hagging","narking","soaping","winding","dealing","earring","cunning","moating","skiting","jutting","fueling","hooping","guiling","mapping","hailing","gutting","firming","bunting","mealing","rending","jobbing","pauling","foiling","peeking","rollins","lansing","felling","whiting","vealing","resting","saltine","earning","purging","mullins","pausing","colling","banning","wasting","sealing","gigging","scaring","pocking","massing","curring","storing","dinging","handing","pitting","faining","cupping","staring","riffing","gowning","hipping","vanning","darting","maiming","damping","deaning","bellini","kipling","marting","hawking","fending","kicking","beading","curving","wending","yelling","foaming","rifting","surging","gaining","stoking","panging","winking","nursing","oinking","looking","tolling","bailing","tanking","hacking","warming","cooping","wanting","rotting","kinking","bugging","purling","wincing","joining","belling","wilting","tensing","fellini","wildi

ng","binding","bugling","sagging","nagging","binging","tatting","cellini","silting","belying","ripping","crating","slaking","killing","hurting","running","harming","banding","rinking","staying","touting","hasting","melting","nibbing","talking","ganging","bonging","rilling","damning","pooling","porting","sinning","collins","barbing","bunking","smiling","hanging","tending","bulging","ginning","coiling","lolling","molting","letting","mending","hinging","gunning","melding","dilling","shaving","harping","basting","cobbing","carting","leading","styling","fowling","goading","yowling","zipping","wagging","gaoling","panning","valving","peeling","titling","sailing","harding","parring","haloing","quiting","punting","reeling","batting","signing","pegging","bogging","mashing","rankine","seeding","sassing","wafting","winging","framing","rooting","longing","sabling","bulbing","whiling","balking","canting","dashing","dueling","renting","booting","whaling","vatting","veining","fencing","yuck

ing","slaving","welling","sunning","lulling","purring","dawning","sensing","meaning","wording","hogging","parsing","falling","yelping","dinning","vetting","hulling","reading","lapsing","tooling","hoaxing","roiling","forming","ramming","gelding","felting","popping","walling","costing","welding","washing","filling","lasting","couping","cabling","getting","winning","carping","martins","bilking","burning","jelling","sicking","tinting","ceiling","totting","balding","kenning","tinging","hugging","westing","burring","pasting","pecking","parking","slaying","pigging","heating","manning","bucking","bussing","gagging","goaling","rowling","netting","funking","pitying","jarring","tasting","putting","beating","funding","mauling","balling","molding","shining","perkins","dialing","panting","looping","welting","relying","dulling","dumping","tanning","warring","gatling","staging","finding","farting","petting","picking","swaying","toiling","jambing","bawling","minting","wedding","hulking","kee

ling","nanking","railing","heading","cutting","gosling","vesting","sighing","mucking","copping","polling","raising","fooling","hooting","titting","calming","seating","rifling","soiling","dubbing","jesting","posting","sacking","corking","yipping","lathing","bopping","setting","coaxing","poshing","fawning","heeling","warning","napping","vending","mooting","hurling","supping","nanjing","pipping","tagging","mopping","souping","palming","gulling","kirking","gilding","docking","wefting","dusting","sharing","darling","bowling","lauding","bidding","hopping","honking","hunting","pepping","busying","damming","patting","hitting","gusting","jigging","gabbing","hosting","sidling","telling","rusting","daubing","reining","memling","healing","gashing","betting","lilting","hashing","salving","firring","gabling","ducking","waiving","skating","worming","waiting","burying","booking","corning","suiting","hooking","gonging","listing","hulaing","sulking","digging","fouling","zincing","cocking","pa

cking","scaling","pooping","zinging","banging","bolling","punning","palling","sipping","bunging","minding","choking","yapping","nicking","warding","gorging","canning","culling","lending","spaying","lashing","pupping","fanning","banking","pinging","roaming","sopping","fonding","searing","fucking","rooking","tooting","raining","billing","pulsing","curbing","cashing","calking","harking","tarring","tacking","whining","tarting","pauline","rasping","howling","helling","curling","pucking","hauling","coaling","lopping","mailing","wailing","lugging","ticking","staving","snaking","selling","masking","jabbing","mewling","heaving","soaring","fagging","cording","begging","ridging","jetting","backing","dotting","lacking","parting","jotting","dunning","tinning","stiling","stating","zapping","hearing","fitting","barging","galling","wigging","feeding","tenting","looting","cabbing","cursing","dunking","dabbing","ragging","bedding","witting","pouting","burping","slating","tamping","basking","f

ailing","papping","narcing","lancing","furlong","tabling","dolling","tailing","pawning","collies","lamming","coifing","bolting","sucking","rafting","morning","ranting","tabbing","rinding","bandung","bashing","bending","ducting","casting","camping","flaming","hinting","sanding","carving","lagging","helping","keening","jolting","temping","junking","manging","dimming","ringing","tipping","spiking","malling","pursing","soaking","willing","fulling","causing","jacking","furring","singing","halting","tucking","ruining","denting","calling","barring","fopping","yawning","tilling","nilling","downing","cooling","martini","budging","lapwing","mincing","rinsing","cowling","marring","coining","sibling","potting","tauting","bulling","lurking","sorting","poohing","bathing","spicing","nailing","spiting","racking","lusting","rutting","gulping","tilting","pairing","peaking","capping","gobbing","finking"]

�
Reply to this email directly or view it on GitHub<
https://github.com/xqian/cpp_projects/issues/10#issuecomment-18898612>
.

�
Reply to this email directly or view it on GitHub<
https://github.com/xqian/cpp_projects/issues/10#issuecomment-18921705>
.

QIAN, Xin (xqian@unh.edu chianshin@gmail.com)
http://www.sciencenet.cn/u/chianshin/

�
Reply to this email directly or view it on GitHubhttps://github.com//issues/10#issuecomment-18921802
.

[xqian]

as to the first point, the cost will be:
N_N_L or
26_L_N*HashComplext

If N is not huge, the first one is OK, but if N is pretty huge, the second
one is better.

Xin Qian

[tj2013]

Hash computing cost is O(L)

More generally, I think this is kind of sparse matrix, so pairwise
comparison is not optimal. Social network is also a sparse matrix.

On Tue, Jun 4, 2013 at 2:18 PM, Xin Qian notifications@github.com wrote:

as to the first point, the cost will be:
N_N_L or
26_L_N*HashComplext

is N is not huge, the first one is OK, but if N is pretty huge, the second
one is better.

Xin Qian

On Tue, Jun 4, 2013 at 1:20 PM, tj2013 notifications@github.com wrote:

I found the dominantly costly part is to calculate neighbors. so I made
two
change

1. instead of compare each pair of strings, cost N * N/2 * L, L is the
   length of string
   for each string, I check all strings who have one character different,
   to
   see if they exist. So the cost is
   for each string, 26 * L * L (second L is to query a hashtable of
   strings)
   total cost is N * 26 * L * L which is much better considering the N and
   L
   of the test cases.

2. instead of calculate all neighbors, I only do it when needed

I think 1) is the major improvement.

On Tue, Jun 4, 2013 at 9:37 AM, Xin Qian notifications@github.com
wrote:

Yes.

How can we improve time complexity?

On Tuesday, June 4, 2013, tj2013 wrote:

so your also could not pass large set. I will profile it.

On Tue, Jun 4, 2013 at 2:36 AM, Xin Qian <notifications@github.com<javascript:_e({},

'cvml', 'notifications@github.com');>>

wrote:

Run Status: Accepted!
Program Runtime: 8 milli secs
Progress: 13/13 test cases passed.
input output expected

"a", "c", ["a","b","c"] [["a","c"]] [["a","c"]]

"hot", "dog", ["hot","dog"] [] []

"hot", "dog", ["hot","dog","dot"] [["hot","dot","dog"]]
[["hot","dot","dog"]]

"hot", "dot", ["hot","dot","dog"] [["hot","dot"]] [["hot","dot"]]

"hot", "dog", ["hot","cog","dog","tot","hog","hop","pot","dot"]
[["hot","hog","dog"],["hot","dot","dog"]]
[["hot","hog","dog"],["hot","dot","dog"]]

"hot", "dog", ["hot","dog","cog","pot","dot"]
[["hot","dot","dog"]]
[["hot","dot","dog"]]

"hit", "cog", ["hot","cog","dot","dog","hit","lot","log"]
[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]

"hit", "cog", ["hot","hit","cog","dot","dog"]
[["hit","hot","dot","dog","cog"]]
[["hit","hot","dot","dog","cog"]]

"red", "tax", ["ted","tex","red","tax","tad","den","rex","pee"]

[["red","ted","tad","tax"],["red","ted","tex","tax"],["red","rex","tex","tax"]]

[["red","ted","tad","tax"],["red","ted","tex","tax"],["red","rex","tex","tax"]]

"lost", "cost", ["most","fist","lost","cost","fish"]
[["lost","cost"]]
[["lost","cost"]]

"lost", "miss", ["most","mist","miss","lost","fist","fish"]
[["lost","most","mist","miss"]] [["lost","most","mist","miss"]]

"leet", "code", ["lest","leet","lose","code","lode","robe","lost"]
[["leet","lest","lost","lose","lode","code"]]
[["leet","lest","lost","lose","lode","code"]]

"talk", "tail", ["talk","tons","fall","tail","gale","hall","negs"]
[]
[]

Run Status: Time Limit Exceeded

Last executed input
"raining", "cellini",

["heaping","conning","nipping","wadding","pulling","lunging","figging","donning","jamming","coating","foaling","ousting","dowsing","busting","penning","lapping","yanking","sapping","tasking","rigging","ranking","larking","farming","dunging","nutting","gouging","barfing","fasting","belting","boiling","boating","dipping","kilning","barking","furling","calving","veiling","decking","ricking","salting","lucking","sending","taiping","marking","martina","warping","bulking","seaming","topping","larding","jilting","besting","weeding","nesting","baiting","jibbing","pelting","bushing","garbing","banting","keeping","venting","rapping","binning","mulling","smiting","hatting","tapping","writing","footing","carding","ratting","bagging","sitting","dousing","pinking","testing","passing","gelling","gassing","ranging","hefting","vamping","wetting","paining","rolling","sinking","yakking","shaking","nabbing","licking","sparing","hamming","celling","halving","matting","landin

g","kooking","pinning","hagging","narking","soaping","winding","dealing","earring","cunning","moating","skiting","jutting","fueling","hooping","guiling","mapping","hailing","gutting","firming","bunting","mealing","rending","jobbing","pauling","foiling","peeking","rollins","lansing","felling","whiting","vealing","resting","saltine","earning","purging","mullins","pausing","colling","banning","wasting","sealing","gigging","scaring","pocking","massing","curring","storing","dinging","handing","pitting","faining","cupping","staring","riffing","gowning","hipping","vanning","darting","maiming","damping","deaning","bellini","kipling","marting","hawking","fending","kicking","beading","curving","wending","yelling","foaming","rifting","surging","gaining","stoking","panging","winking","nursing","oinking","looking","tolling","bailing","tanking","hacking","warming","cooping","wanting","rotting","kinking","bugging","purling","wincing","joining","belling","wilting","tensing","fellini","wildi

ng","binding","bugling","sagging","nagging","binging","tatting","cellini","silting","belying","ripping","crating","slaking","killing","hurting","running","harming","banding","rinking","staying","touting","hasting","melting","nibbing","talking","ganging","bonging","rilling","damning","pooling","porting","sinning","collins","barbing","bunking","smiling","hanging","tending","bulging","ginning","coiling","lolling","molting","letting","mending","hinging","gunning","melding","dilling","shaving","harping","basting","cobbing","carting","leading","styling","fowling","goading","yowling","zipping","wagging","gaoling","panning","valving","peeling","titling","sailing","harding","parring","haloing","quiting","punting","reeling","batting","signing","pegging","bogging","mashing","rankine","seeding","sassing","wafting","winging","framing","rooting","longing","sabling","bulbing","whiling","balking","canting","dashing","dueling","renting","booting","whaling","vatting","veining","fencing","yuck

ing","slaving","welling","sunning","lulling","purring","dawning","sensing","meaning","wording","hogging","parsing","falling","yelping","dinning","vetting","hulling","reading","lapsing","tooling","hoaxing","roiling","forming","ramming","gelding","felting","popping","walling","costing","welding","washing","filling","lasting","couping","cabling","getting","winning","carping","martins","bilking","burning","jelling","sicking","tinting","ceiling","totting","balding","kenning","tinging","hugging","westing","burring","pasting","pecking","parking","slaying","pigging","heating","manning","bucking","bussing","gagging","goaling","rowling","netting","funking","pitying","jarring","tasting","putting","beating","funding","mauling","balling","molding","shining","perkins","dialing","panting","looping","welting","relying","dulling","dumping","tanning","warring","gatling","staging","finding","farting","petting","picking","swaying","toiling","jambing","bawling","minting","wedding","hulking","kee

ling","nanking","railing","heading","cutting","gosling","vesting","sighing","mucking","copping","polling","raising","fooling","hooting","titting","calming","seating","rifling","soiling","dubbing","jesting","posting","sacking","corking","yipping","lathing","bopping","setting","coaxing","poshing","fawning","heeling","warning","napping","vending","mooting","hurling","supping","nanjing","pipping","tagging","mopping","souping","palming","gulling","kirking","gilding","docking","wefting","dusting","sharing","darling","bowling","lauding","bidding","hopping","honking","hunting","pepping","busying","damming","patting","hitting","gusting","jigging","gabbing","hosting","sidling","telling","rusting","daubing","reining","memling","healing","gashing","betting","lilting","hashing","salving","firring","gabling","ducking","waiving","skating","worming","waiting","burying","booking","corning","suiting","hooking","gonging","listing","hulaing","sulking","digging","fouling","zincing","cocking","pa

cking","scaling","pooping","zinging","banging","bolling","punning","palling","sipping","bunging","minding","choking","yapping","nicking","warding","gorging","canning","culling","lending","spaying","lashing","pupping","fanning","banking","pinging","roaming","sopping","fonding","searing","fucking","rooking","tooting","raining","billing","pulsing","curbing","cashing","calking","harking","tarring","tacking","whining","tarting","pauline","rasping","howling","helling","curling","pucking","hauling","coaling","lopping","mailing","wailing","lugging","ticking","staving","snaking","selling","masking","jabbing","mewling","heaving","soaring","fagging","cording","begging","ridging","jetting","backing","dotting","lacking","parting","jotting","dunning","tinning","stiling","stating","zapping","hearing","fitting","barging","galling","wigging","feeding","tenting","looting","cabbing","cursing","dunking","dabbing","ragging","bedding","witting","pouting","burping","slating","tamping","basking","f

ailing","papping","narcing","lancing","furlong","tabling","dolling","tailing","pawning","collies","lamming","coifing","bolting","sucking","rafting","morning","ranting","tabbing","rinding","bandung","bashing","bending","ducting","casting","camping","flaming","hinting","sanding","carving","lagging","helping","keening","jolting","temping","junking","manging","dimming","ringing","tipping","spiking","malling","pursing","soaking","willing","fulling","causing","jacking","furring","singing","halting","tucking","ruining","denting","calling","barring","fopping","yawning","tilling","nilling","downing","cooling","martini","budging","lapwing","mincing","rinsing","cowling","marring","coining","sibling","potting","tauting","bulling","lurking","sorting","poohing","bathing","spicing","nailing","spiting","racking","lusting","rutting","gulping","tilting","pairing","peaking","capping","gobbing","finking"]

�
Reply to this email directly or view it on GitHub<

https://github.com/xqian/cpp_projects/issues/10#issuecomment-18898612>

.

�
Reply to this email directly or view it on GitHub<
https://github.com/xqian/cpp_projects/issues/10#issuecomment-18921705>

.

QIAN, Xin (xqian@unh.edu chianshin@gmail.com)
http://www.sciencenet.cn/u/chianshin/

�
Reply to this email directly or view it on GitHub<
https://github.com/xqian/cpp_projects/issues/10#issuecomment-18921802>
.

�
Reply to this email directly or view it on GitHub<
https://github.com/xqian/cpp_projects/issues/10#issuecomment-18936231>
.

QIAN, Xin (xqian@unh.edu chianshin@gmail.com)
http://www.sciencenet.cn/u/chianshin/

�

Reply to this email directly or view it on GitHubhttps://github.com//issues/10#issuecomment-18939952
.