Minimum Single-Character Steps to a Target String

You are given two strings start and target, each exactly 8 characters long and using only the letters A, C, G, and T. You are also given a dictionary of such strings.

A step changes exactly one character of the current string to one of the four letters. Every string produced by a step, including the final one, must appear in dictionary. start itself does not need to appear in dictionary.

Return the minimum number of steps needed to turn start into target. If start equals target, the answer is 0. If there is no sequence of steps that reaches target, return -1.

Examples

Example 1

Input: start = "AACCGGTT", target = "AACCGGTA", dictionary = ["AACCGGTA"]
Output: 1

Example 2

Input: start = "AACCGGTT", target = "AAACGGTA", dictionary = ["AACCGGTA","AACCGCTA","AAACGGTA"]
Output: 2