NeetCode #759LC-514Hard2-D Dynamic Programming
← Back to All Problems#759 · #514 · Freedom Trail(自由之路)
📌 Problem Statement & Constraints
The string
ring is written around a dial with index 0 at the top, and a center button can be pressed. To spell key, rotate the ring so the needed character is at the top (one step per position, either direction) and press the button (one step). Return the minimum total steps to spell the entire key. Constraints: 1 <= ring.length, key.length <= 100, and key is spellable from ring.💡 Core Algorithmic Approaches
- Let
dp[pos]be the minimum steps to spell the key prefix processed so far with the ring rotated so that indexposis at the top. - For the next key character, gather every ring index holding that character; each is a candidate new state.
- The rotation cost from a previous position
prevtocurismin(|cur - prev|, n - |cur - prev|), plus 1 for the button press. - The answer is the minimum over all states after the final character.
💻 Benchmark Python3 Implementation
class Solution:
def findRotateSteps(self, ring: str, key: str) -> int:
from collections import defaultdict
n = len(ring)
pos = defaultdict(list)
for i, ch in enumerate(ring):
pos[ch].append(i)
dp = {0: 0} # current top index -> min steps
for ch in key:
nxt = {}
for cur in pos[ch]:
best = float("inf")
for prev, cost in dp.items():
dist = abs(cur - prev)
dist = min(dist, n - dist) # clockwise vs counter-clockwise
best = min(best, cost + dist + 1)
nxt[cur] = best
dp = nxt
return min(dp.values())⚡ Complexity Deep Dive
⏱️ Time Complexity
O(k * r^2) worst case: each key character may match many ring positions, each compared against all previous positions.
💾 Space Complexity
O(r): one dictionary of position costs.
⚠️ Interview Pitfalls & Follow-ups
- Rotating only clockwise: the dial turns both ways, so the cost is
min(dist, n - dist). - Forgetting the button press: each matched character costs one extra step to press the center button.
- Choosing the nearest occurrence greedily: a locally near occurrence can be globally worse, so the DP must consider every matching position.
- Keeping a single best position per character: several ring indices may hold the same character, and each is a distinct DP state.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.