Best Way to Solve Word Chain
I am trying to solve this problem in CodeEval.
In this problem, we invite you to play the famous game "Word chain", in which the players come up with words that begin with the letter that the previous word ended. The challenge is to determine the maximum length of a string 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: "soup-> peas-> sugar-> rice".
Limitations:
- The length of the word list is in the range [4, 35].
- The word in the wordlist is represented by a random ascii lowercase string with length [3, 7] letters.
- There are no duplicate words in the word list.
My attempt . My approach is to model the words as a graph so that each word in the inputs is a node and there is a (directed) edge between wordi and wordj if the last character of the word i is equal to the first character of the word.
After that I run bfs from each node and calculate the length of the farthest node from that node. The end result is the maximum value possible for all nodes.
But this approach does not give me a complete assessment. Hence my question is how to solve this problem correctly and efficiently?
source to share
For my reputation less than 50, so I cannot comment ...
If the total word count is less than 20, we can solve using dynamic programming and bitmask. do dp [20] [1 <20]. dp [i] [j] means that you are currently at i and you are visiting the j word bitmask.
For a number greater than 20, I still don't have a good idea. Maybe we need to use some kind of random algorithm, maybe ....
My idea is to use dfs and add some optimization because 35 is not too big. I think this is enough to solve the problem.
source to share
See the solution mentioned here: Detecting when matrix multiplication is possible
The solution to your problem is almost the same. Create a directed graph such that an edge is added for each job from the first letter to the last letter.
Then find the Euler path ( http://en.wikipedia.org/wiki/Euler_path ) in that graph.
EDIT: I see that you are not sure about using all the words and you want the longest path in the graph ( http://en.wikipedia.org/wiki/Longest_path_problem ). This problem is NP-complete.
source to share
See the solution mentioned in word chain in the kernel kernel
The page gives a solution in Core Java, this follows the following process:
- Load Dictionary elements into memory for a given word length
- Get the next matching list of words from memory for a given word
There is another approach using Map / reduce hadoop framework which is detailed in chain of words using map-reduce
source to share