886. Dial the Ring
A safe has a circular dial ring: a string of lowercase letters laid out clockwise, with a fixed pointer that initially rests on index 0. In one move you may turn the dial one letter clockwise or one letter anticlockwise (the string wraps around), which shifts the pointer by one index in that direction.
To open the safe you must enter the word key one letter at a time and in order: when the pointer rests on a position holding the next letter you press the confirm button, which also counts as one move. Every letter of key occurs somewhere on the ring, and the same ring position may be confirmed repeatedly. Return the minimum total number of moves (turns plus presses) needed to enter the whole key.
Example 1
- Input:
- ring = "lanterns", key = "str"
- Output:
- 10
- Explanation:
Turn 1 back to s, 4 to t, 2 to r: 7 turns plus 3 presses = 10.
Example 2
- Input:
- ring = "quartz", key = "zzaq"
- Output:
- 10
- Explanation:
1 turn to the first z, press twice with no turning, 3 turns to a, 2 turns to q: 6 turns plus 4 presses = 10.
Example 3
- Input:
- ring = "abcabc", key = "ccc"
- Output:
- 4
- Explanation:
One anticlockwise turn reaches the c at index 5, then three presses: 4 moves.
Constraints
- 1 ≤ ring.length ≤ 2000
- 1 ≤ key.length ≤ 2000
- Both strings consist of lowercase English letters, and every letter of
keyappears inring
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 800 msC++ 200 msJava 400 msJavaScript 400 msTypeScript 400 ms
Expected complexity
- Time
- O(n * m)
- Space
- O(n)