Spelling a Word on a Dial Lock

Hard

A lock opens with a code word typed on a round dial. The letters of the string dial are engraved around the dial, with the first one following the last. There is a mark at the top, and dial[0] starts under it. The word word is typed one letter at a time: - turning the dial by one position, clockwise or counterclockwise, is one step; - once the needed letter is under the mark, pressing the center button is one more step. Return the minimum number of steps to type all of word. Every letter of it is guaranteed to be on the dial.

Example 1

dial="carton", word="tan" → 10

t is three steps from the mark: 3 turns and a press. Then a is 2 steps away plus a press, and n is 2 steps away going past the start of the ring, plus a press. In total, 4 + 3 + 3 = 10.

Example 2

dial="abcabc", word="ca" → 4

It is better to use the c at the end of the ring: 1 turn back and a press. From there the a at the start is 1 more turn and a press. In total, 4.

Example 3

dial="z", word="zzz" → 3

No turning is needed, just three presses.

Constraints

1 ≤ len(dial), len(word) ≤ 100
Both strings consist of lowercase English letters
Every letter of word appears in dial

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Breadth-First Search String Dynamic Programming