Loading...
Loading...
Loading...
A college word club plays a game. You get a start word, a target word and a list of allowed words, all of the same length.
In one change, you replace exactly one letter of the current word with another letter. The new word must be in the allowed list. The start word itself does not have to be in the list.
Print the fewest changes needed to turn the start word into the target word. If the start and target are the same, print 0. If it cannot be done, print -1.
Example 1
Input
cold warm 6 cord card ward warm word worm
Output
4
One shortest way is cold → cord → card → ward → warm: 4 changes.
Example 2
Input
pen ink 3 pin pit ink
Output
-1
pen can become pin, and pin can become pit, but neither is one letter away from ink.
Try the problem first. Open one hint at a time.
Treat each word as a point, and join two words when they differ in exactly one letter. The question becomes a shortest path where every step costs 1.
When every step costs the same, a level-by-level search from the start finds the fewest steps.
To find the neighbours of a word, try changing each position to each of the 26 letters and check a HashSet of allowed words.
Mark a word as seen when you add it to the queue, so it is never added twice. Handle start equal to target before searching.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor