Word Ladder
Real-world version: Dial Code RewriteThe statement here is our own: the same inputs, outputs and technique.
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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def shortest_rewrite(startCode: str, targetCode: str, approved: list[str]) -> int:public int shortestRewrite(String startCode, String targetCode, List<String> approved)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 10 test cases: 10 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's