You are given a circular ring represented by a string ring, and a keyword represented by a string key that you need to spell out.
Initially, the first character of ring (index key sequentially, you must:
Rotate the ring clockwise or anticlockwise. Each rotation by one position counts as one step. Rotate until a character in ring that matches the current target character key[i] is aligned at the "12:00" position.
Press the center button to confirm the character, which counts as one additional step.
After pressing, you move on to spell the next character in key. The ring is circular, meaning its last character wraps around to its first character.
Return the minimum total number of steps required to spell all characters in key.
Note: Each button press counts as one step in addition to the rotation steps.
Constraints:
ring.length, key.length
ring and key consist of only lowercase English letters.
It is guaranteed that key can always be spelled by rotating ring.
The key insight is that this problem has optimal substructure and overlapping subproblems, making it ideal for dynamic programming. At each step, we need to spell the next character in key by rotating the ring to align a matching character at the "12:00" position. Since the same character may appear at multiple positions in ring, we must consider all possible positions and choose the one that minimizes total cost. We define a recursive function dp(keyIdx, ringPos) that returns the minimum number of steps to spell ...
You are given a circular ring represented by a string ring, and a keyword represented by a string key that you need to spell out.
Initially, the first character of ring (index key sequentially, you must:
Rotate the ring clockwise or anticlockwise. Each rotation by one position counts as one step. Rotate until a character in ring that matches the current target character key[i] is aligned at the "12:00" position.
Press the center button to confirm the character, which counts as one additional step.
After pressing, you move on to spell the next character in key. The ring is circular, meaning its last character wraps around to its first character.
Return the minimum total number of steps required to spell all characters in key.
Note: Each button press counts as one step in addition to the rotation steps.
Constraints:
ring.length, key.length
ring and key consist of only lowercase English letters.
It is guaranteed that key can always be spelled by rotating ring.
The key insight is that this problem has optimal substructure and overlapping subproblems, making it ideal for dynamic programming. At each step, we need to spell the next character in key by rotating the ring to align a matching character at the "12:00" position. Since the same character may appear at multiple positions in ring, we must consider all possible positions and choose the one that minimizes total cost. We define a recursive function dp(keyIdx, ringPos) that returns the minimum number of steps to spell ...