Gene Edit Chain

Medium

A gene is a string of exactly 8 characters, each one of A, C, G or T. One edit replaces a single character of the string with another. A lab wants to turn gene start into gene goal through a sequence of edits. After every edit the result must be a viable gene, meaning a string from the list allowed. start itself counts as viable even if it is not on the list. Return the fewest edits needed, or -1 if it cannot be done.

Example 1

start="GATTACAA", goal="GATTACCC", allowed=["GATTACCA", "GATTACCC"] → 2

GATTACAA → GATTACCA → GATTACCC: two edits, and every intermediate string is in allowed.

Example 2

start="GATTACAA", goal="GATTACCC", allowed=["GATTACCC"] → -1

The goal is two letters away and there is no allowed gene in between, so the answer is -1.

Example 3

start="CCCCCCCC", goal="CCCCCCCC", allowed=[] → 0

Constraints

len(start) == len(goal) == len(allowed[i]) == 8
0 ≤ len(allowed) ≤ 10
Strings contain only the characters A, C, G, T

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Breadth-First Search Hash Table String

Similar problems

Merge Contact Cards Medium Chains of Synonyms Medium Turning a Combination Lock Medium Rearrange Through Links Medium Smallest Shared Territory Medium

Input

start="GATTACAA", goal="GATTACCC", allowed=["GATTACCA", "GATTACCC"]

Expected

Run checks the first 3 tests in your browser. Submit checks all 61 tests on the server, hidden ones included.