All problems

Spell Shift Ladder

Hard · shortest path

An apprentice wizard changes one word into another by altering a single letter at a time. The spell-book only knows the words in words: every word the apprentice turns into, including the final goal, must be one of them. All words have the same length and use lowercase English letters.

One step changes exactly one letter of the current word into a different letter. A step costs as much magic as the distance between the two letters in the alphabet, so changing a into d costs 3 and changing d into a also costs 3. The alphabet does not wrap round: a to z costs 25.

The word start does not have to be in words, and words may contain the same word more than once. start and goal are always different.

Return the smallest total cost of any sequence of steps that turns start into goal, or -1 if it cannot be done.

Examples

Example 1

Input: start = "bb", goal = "dd", words = ["ab", "ad", "dd"]

Output: 6

The only way is "bb" -> "ab" (cost 1) -> "ad" (cost 2) -> "dd" (cost 3).

Example 2

Input: start = "cat", goal = "dog", words = ["cot", "dot"]

Output: -1

"dog" is not in the list, so it can never be reached.

Example 3

Input: start = "aa", goal = "cc", words = ["ea", "ec", "cc", "ab", "bb", "bc"]

Output: 4

Going "aa" -> "ab" -> "bb" -> "bc" -> "cc" takes four steps of cost 1 each. The shorter route "aa" -> "ea" -> "ec" -> "cc" has only three steps but costs 4 + 2 + 2 = 8.

Constraints