Freedom Trail
Hard · Dynamic Programming · String · Dynamic Programming · Depth-First Search · Breadth-First Search
Problem
A combination dial shows the letters of the string ring around its edge, in order, with ring[0] starting at the 12 o'clock mark. You must spell the string key, one letter at a time.
Each step is one of: - Rotate the dial one position clockwise or anticlockwise (one step). - Press the center button (one step). This spells the letter at 12 o'clock, and it must be the next letter of key.
Return the fewest steps needed to spell all of key. Every letter of key appears somewhere in ring.
Examples
Input: ring = "abcde", key = "ade" Output: 6
Press for "a" (1 step). Rotate two positions anticlockwise to "d" and press (3). Rotate one position to "e" and press (2). Total 6.
Input: ring = "aaa", key = "aa" Output: 2
"a" is already at 12 o'clock; press twice.
Input: ring = "godding", key = "gd" Output: 4
Press for the "g" at 12 o'clock (1). The nearest "d" is two positions clockwise, at index 2: rotate twice and press (3). Total 4.
Constraints
- 1 <= len(ring), len(key) <= 100
- ring and key consist of lowercase English letters.
- Every letter of key occurs in ring.
Approaches
- Try every choice of copy — time O(R^m) worst case, space O(m) recursion
Follow-up
The press steps always add len(key), so the real question is the shortest rotation path. Seen as a graph with one layer per key letter, it is a shortest path in a layered DAG; Dijkstra over (letter index, position) works too, and the layer-by-layer DP is that shortest path computed in topological order.
Related problems
Start free on Cariara · Coding problems · System design studio
