3

I am trying to solve this problem in CodeEval.

In this challenge we suggest you to play in the known game "Word chain" in which players come up with words that begin with the letter that the previous word ended with. The challenge is to determine the maximum length of a chain that can be created from a list of words.

Example:

Input:

soup,sugar,peas,rice

Ouput:
4

Explanation: We can form a chain of 4 words like this: "soup->peas->sugar->rice".

Constraints:

  • The length of a list of words is in range [4, 35].
  • A word in a list of words is represented by a random lowercase ascii string with the length of [3, 7] letters.
  • There is no repeating words in a list of words.

My attempt: My approach is to model the words as a graph, such that each word in the inputs represents a node and there is an (directed) edge between from wordi to wordj if last character of wordi is equal to the first character of wordj.

After that I am running bfs from each node and computing the length of the farthest node from the this node. The final result is the maximum value possible for all nodes.

But this approach is not giving me a full score. Hence, my question is how to solve this problem correctly and efficiently?

Quixotic
  • 2,424
  • 7
  • 36
  • 58
  • I he builds a tree there shouldn't be a cycle. For each node you know the list of the remaining candidates for the child node. – Steve K Aug 06 '14 at 03:18
  • @SteveK hmm, `sos` alone is a cycle, so the length can be infinite – Pham Trung Aug 06 '14 at 03:25
  • @Pham - if you start the tree with `sos` the list of remaining candidates will be `{}`. Very hard to produce a cycle from an empty list. – Jan Groth Aug 06 '14 at 03:26
  • @jangroth I don't see any constraint to stop you reuse a word :) – Pham Trung Aug 06 '14 at 03:28
  • @Pham Then I suggest you follow the link that the OP provided and read the last sentence on the page. – Jan Groth Aug 06 '14 at 03:32
  • @jangroth the list of word is just the input, If I am not wrong. – Pham Trung Aug 06 '14 at 03:33
  • 1
    @Pham I agree that there is tiny space for (miss-)interpretation. But if you were right the constraint would have close to zero impact on the algorithm itself. So I'd say you're rather wrong, because I assume the constraint is there for a reason. Anyhow, this is getting a bit pointless, specially because we lost the OP... :) – Jan Groth Aug 06 '14 at 03:40
  • 1
    @jangroth Ha ha, totally agree :) – Pham Trung Aug 06 '14 at 03:43
  • @Pham: If you consider the input as vector then it is of size [4,35]. So yes it gives bound on the number of words in the input. And each word will be of length [3,7] lower case ascii characters. I think the constraints are pretty clear though :) – Quixotic Aug 06 '14 at 05:23
  • By length of chain do you mean number of words or number of letters in the chain? – Abhishek Bansal Aug 06 '14 at 07:54
  • @user1990169 look at the example, so I think it should be the number of words – Pham Trung Aug 06 '14 at 09:42
  • possible duplicate of [Shortest path to transform one word into another](http://stackoverflow.com/questions/1521958/shortest-path-to-transform-one-word-into-another) – outis Jul 11 '15 at 01:19

3 Answers3

0

For my reputation is less than 50, so I can't make a comment...

If the total number of word is less than 20, we can solve using dynamic programming and bitmask. make dp[20][1<<20]. dp[i][j] means currently you are in i, and you have visit the bitmask j's word.

For number is bigger than 20, I still haven't a good idea. May be we need to use some random algorithm, perhaps...。

My idea is to use dfs and add some optimizaion, because 35 is not too big. I think it's enough to solve the problem.

mickeyandkaka
  • 1,452
  • 2
  • 11
  • 21
0

See the solution mentioned here: Detecting when matrix multiplication is possible

The solution to your problem is pretty much same. Create a directed graph such that for every work add an edge from first letter to last letter.

Then find a Euler path ( http://en.wikipedia.org/wiki/Euler_path ) in that graph.

EDIT: I see that you are not assured of using all words and you need the longest path in the graph ( http://en.wikipedia.org/wiki/Longest_path_problem ). This problem is NP-complete.

Community
  • 1
  • 1
ElKamina
  • 7,747
  • 28
  • 43
0

See the solution mentioned word chain in core java

The page gives a solution in Core Java, it follows the following process:

  1. Load the Dictionary Items in memory for a given word length
  2. Get the next eligible list of words from the memory for the given word

There is another approach using the Map/reduce hadoop framework, which is mentioned in detail in the word chain using map-reduce

Pankaj Khattar
  • 111
  • 1
  • 10