0055HardHash TableStringBreadth-First SearchBidirectional Search

Dial Code Rewrite

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A stockroom cabinet is held shut by a row of letter dials that currently spell startCode. You want the dials to spell targetCode instead.

Spinning a single dial rewrites exactly one position of the current code, and the cabinet's firmware refuses to settle on anything it does not recognise: after every single spin, the code showing on the dials must be one of the strings in approved. startCode is where you begin so it does not have to be listed, but targetCode does, since the dials have to settle on it.

Count the codes along the shortest run of spins that gets from startCode to targetCode, including startCode and targetCode themselves. Two codes in a row along that run differ at exactly one position. When the dials cannot reach targetCode at all, report 0.

Examples

Example 1

Input: startCode = "cold", targetCode = "warm", approved = ["cord", "card", "ward", "warm", "word", "wart"]
Output: 5

The dials can go cold, cord, card, ward, warm, which is five codes. Nothing shorter works, because cold and warm disagree at all four positions and so at least four spins are needed.

Example 2

Input: startCode = "cold", targetCode = "warm", approved = ["cord", "card", "ward", "word", "wart"]
Output: 0

The target itself is absent from the approved strings, so the firmware would never let the dials rest on it.

Example 3

Input: startCode = "damp", targetCode = "lamp", approved = ["lamp", "dame", "lame"]
Output: 2

One spin of the leading dial reaches an approved target, so the run holds just the two codes.

Constraints

1 <= startCode.length <= 10
targetCode.length == startCode.length
1 <= approved.length <= 5000
approved[i].length == startCode.length
startCode, targetCode and approved[i] consist of lowercase English letters
startCode != targetCode
All strings in approved are distinct

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def shortest_rewrite(startCode: str, targetCode: str, approved: list[str]) -> int:

Java

public int shortestRewrite(String startCode, String targetCode, List<String> approved)

The intended approach

Time O(26 * n * L^2) for n approved strings of length LSpace O(n * L)

Because every spin costs the same, the shortest run is a breadth-first sweep outward from `startCode` over the approved strings. Hold the approved strings in a set and expand a code by trying all 25 replacement letters at each position, keeping only the rewrites the set recognises. Drop each code from the set the moment it is queued, which both marks it as reached and keeps the sweep from revisiting it, so every approved string is expanded at most once. An empty queue means the target was never reached.

Pythonentry point: shortest_rewrite

def shortest_rewrite(startCode, targetCode, approved):
    from collections import deque
    pool = set(approved)
    if targetCode not in pool:
        return 0
    pool.discard(startCode)
    alphabet = "abcdefghijklmnopqrstuvwxyz"
    queue = deque()
    queue.append((startCode, 1))
    while queue:
        code, seen = queue.popleft()
        if code == targetCode:
            return seen
        for i in range(len(code)):
            for letter in alphabet:
                if letter == code[i]:
                    continue
                candidate = code[:i] + letter + code[i + 1:]
                if candidate in pool:
                    pool.remove(candidate)
                    queue.append((candidate, seen + 1))
    return 0

The obvious version

Treat the start plus every approved string as vertices, decide adjacency by comparing two strings position by position and demanding exactly one mismatch, then relax the counts repeatedly until a full pass changes nothing. Cubic in the number of strings and it never builds a candidate rewrite.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_shortest_rewrite(startCode, targetCode, approved):
    if targetCode not in approved:
        return 0
    nodes = [startCode] + [w for w in approved if w != startCode]
    n = len(nodes)

    def one_apart(a, b):
        gaps = 0
        for x, y in zip(a, b):
            if x != y:
                gaps += 1
                if gaps > 1:
                    return False
        return gaps == 1

    counts = [None] * n
    counts[0] = 1
    for _ in range(n):
        moved = False
        for i in range(n):
            if counts[i] is None:
                continue
            for j in range(n):
                if i == j or not one_apart(nodes[i], nodes[j]):
                    continue
                if counts[j] is None or counts[j] > counts[i] + 1:
                    counts[j] = counts[i] + 1
                    moved = True
        if not moved:
            break
    goal = nodes.index(targetCode)
    return 0 if counts[goal] is None else counts[goal]

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in