Show problems as
Classic problem #433MediumHash TableStringBreadth-First SearchBidirectional Search

Minimum Genetic Mutation

Real-world version: Retooling the Bottling Line
Tracked in this browser only
Read Minimum Genetic Mutation on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A bottling line has eight stations in a row, and each station carries one of four nozzle types, written "A", "C", "G" or "T". A fitting of the whole line is therefore a string of exactly eight of those letters, read from the first station to the last.

The line is currently on the fitting start and the shift plan calls for the fitting target. A single retool takes the line down and swaps the nozzle on exactly one station, leaving the other seven alone.

Safety rules only allow the line to run on a fitting drawn from approved. Every fitting the line comes to rest on, including target, has to be on that list. The fitting the line starts on does not have to be on the list, since it is already running. The list may be empty and may name the same fitting more than once.

Return the fewest retools that take the line from start to target, or -1 when no run of retools does.

Examples

Example 1

Input
start = "AACCGGTT", target = "AACCGAAA", approved = ["AACCGGTA", "AACCGGAA", "AACCGAAA", "TTTTTTTT"]
Output
3

Swapping station 8, then station 7, then station 6 gets there, and each of the three fittings the line rests on is on the approved list.

Example 2

Input
start = "AACCGGTT", target = "AACCGAAA", approved = ["AACCGGAA", "AACCGAAA"]
Output
-1

Each approved fitting here differs from the current one on two stations, and a retool touches one station, so the line has nowhere legal to rest.

Example 3

Input
start = "AACCGGTT", target = "AACCGGTT", approved = []
Output
0

The line already carries the fitting the shift plan asks for, so no station is touched.

Constraints

  • 0 <= approved.length <= 10
  • len(start) == len(target) == len(approved[i]) == 8
  • start, target and approved[i] consist only of the characters 'A', 'C', 'G' and 'T'.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def fewest_retools(start: str, target: str, approved: list[str]) -> int:
Java
public int fewestRetools(String start, String target, String[] approved)

More on the same topics