Shortest String That Contains All Words

added by KodefuGuru
1/3/2012 2:11:10 AM

7 Kicks, 304 Views

Mango12 created an interesting competition to kick off the New Year, and I decided to try it out. It’s a simple task along the lines of a code kata, and I recommend you try it yourself before looking over my solution. Task: Compress a list of words into the shortest string that contains all words. Test: “testing”, “ginger”, “german”, “minutes” should become “minutestingingerman” Here is my approach: create a weighted graph connecting each term then recursively reduce the highest weighted edges.


1 comments

dpeterson
1/3/2012 10:33:19 AM
Wish I had the time to give this a shot, looks like a fun Kata.