Marquee Letter Swaps
An old cinema has a sign above the door made of loose letter tiles. As a running joke with the neighborhood, the manager changes it a little every night: she climbs the ladder once and swaps exactly one tile. The rule regulars love is that the sign must always show a real word from the house list of approved words.
Tonight it says cold, and for the winter festival she wants it to say warm. Each night is one tile swap, so the path might run cold → cord → word → ward → warm. How few nights can it take?
Your task
Write nightsToChange(current, target, approved). Each night you change exactly one letter of the sign, and the new word must be in approved. Return the fewest nights needed to go from current to target, or -1 if it cannot be done.
current does not have to be in approved (it is already on the sign), but target and every word in between do. If current equals target, return 0. All words have the same length and use lowercase letters a to z.
nightsToChange(current: string, target: string, approved: string[]) → int
Examples
current = "cold" target = "warm" approved = ["cord", "card", "word", "ward", "warm", "worm", "core"]
4
One shortest path is cold → cord → word → worm → warm. Each step changes one letter and lands on an approved word. Every letter of cold differs from warm, so at least 4 nights are needed, and 4 is enough.
current = "hat" target = "hot" approved = ["hit", "hut"]
-1
hat and hot differ by one letter, but hot is not on the approved list, so the sign can never show it. Return -1.
current = "ab" target = "ba" approved = ["aa", "bb", "ba"]
2
ab → aa → ba or ab → bb → ba. Two nights.
Constraints
- 1 ≤ word length ≤ 8
- 0 ≤ approved.length ≤ 2,000
- current, target and every approved word have the same length
- approved has no duplicates
Start with brute force
Build the full graph first by comparing every pair of approved words letter by letter, then run breadth-first search. With 2,000 words that is about 2 million pairs, each compared up to 8 letters. It works, but building the graph is the slow part.
The worse idea is to change letters greedily toward the target, only touching positions that are still wrong. Sometimes the only path moves a correct letter away and back. Going from aa to bb with only ac, bc and bb approved, neither ba nor ab is allowed, so you must go aa → ac → bc → bb. Greedy gives up there even though a real path exists.
Hints
0 of 4 shown- Hint 1
Draw each approved word as a dot, and join two dots when they differ in exactly one letter. In that picture, what is the question really asking?
- Hint 2
It asks for the fewest edges from
currenttotarget. Every night costs the same, so which search finds the fewest steps? - Hint 3
Breadth-first search works, but you must find a word's neighbors fast. Comparing it to all 2,000 approved words each time is slow. A word of length L has only 25 × L one-letter changes. Could you generate those and check them against a set?
- Hint 4
Put the approved words in a set. Run breadth-first search from
current, level by level. For each word, try every position and every letter; if the new word is in the set, it is a neighbor: remove it from the set (so it is never queued twice) and queue it with nights + 1. Return the count when you producetarget, or -1 when the queue runs out.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
The words form a graph: two words are neighbors when they differ in one letter. Every night is one edge, so the fewest nights is the shortest path, and with equal-cost edges that is breadth-first search. The hard part is finding neighbors quickly, without ever building the whole graph.
Generate neighbors instead of searching for them. A 4-letter word has 4 × 25 = 100 one-letter variations; check each against a set of approved words. Remove a word from the set when you first reach it, which serves as the visited mark.
Trace the first example, cold → warm:
- Night 1, from cold: the variations in the set are cord. Level: [cord].
- Night 2, from cord: word, card and core. Level: [word, card, core].
- Night 3: from word, ward and worm. card and core lead nowhere new, because ward is already taken. Level: [ward, worm].
- Night 4: from ward, changing d to m gives warm, the target. Return 4.
Two details matter. Check that target is approved before starting, or you will search everything for nothing. And process the search level by level so that nights counts levels, not words.
function nightsToChange(current, target, approved) {
if (current === target) return 0;
const unused = new Set(approved); // approved words not yet reached
if (!unused.has(target)) return -1;
const letters = 'abcdefghijklmnopqrstuvwxyz';
let level = [current];
let nights = 0;
while (level.length > 0) {
nights++;
const next = [];
for (const word of level) {
for (let i = 0; i < word.length; i++) {
for (const ch of letters) {
if (ch === word[i]) continue;
const cand = word.slice(0, i) + ch + word.slice(i + 1);
if (!unused.has(cand)) continue;
if (cand === target) return nights;
unused.delete(cand); // first time reached = fewest nights
next.push(cand);
}
}
}
level = next;
}
return -1;
}def nights_to_change(current, target, approved):
if current == target:
return 0
unused = set(approved) # approved words not yet reached
if target not in unused:
return -1
letters = 'abcdefghijklmnopqrstuvwxyz'
level = [current]
nights = 0
while level:
nights += 1
nxt = []
for word in level:
for i in range(len(word)):
for ch in letters:
if ch == word[i]:
continue
cand = word[:i] + ch + word[i + 1:]
if cand not in unused:
continue
if cand == target:
return nights
unused.discard(cand) # first time reached = fewest nights
nxt.append(cand)
level = nxt
return -1Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.