|
1 | 1 | package com.fishercoder.solutions;
|
2 | 2 |
|
3 |
| -/** |
4 |
| - * 514. Freedom Trail |
5 |
| - * |
6 |
| - * In the video game Fallout 4, the quest "Road to Freedom" requires players to reach a metal dial called |
7 |
| - * the "Freedom Trail Ring", and use the dial to spell a specific keyword in order to open the door. |
8 |
| -
|
9 |
| - Given a string ring, which represents the code engraved on the outer ring and another string key, |
10 |
| - which represents the keyword needs to be spelled. |
11 |
| - You need to find the minimum number of steps in order to spell all the characters in the keyword. |
12 |
| -
|
13 |
| - Initially, the first character of the ring is aligned at 12:00 direction. |
14 |
| - You need to spell all the characters in the string key one by one by |
15 |
| - rotating the ring clockwise or anticlockwise to make each character of the string key |
16 |
| - aligned at 12:00 direction and then by pressing the center button. |
17 |
| -
|
18 |
| - At the stage of rotating the ring to spell the key character key[i]: |
19 |
| - You can rotate the ring clockwise or anticlockwise one place, which counts as 1 step. |
20 |
| - The final purpose of the rotation is to align one of the string ring's characters at the 12:00 direction, |
21 |
| - where this character must equal to the character key[i]. |
22 |
| - If the character key[i] has been aligned at the 12:00 direction, |
23 |
| - you need to press the center button to spell, which also counts as 1 step. |
24 |
| - After the pressing, you could begin to spell the next character in the key (next stage), otherwise, you've finished all the spelling. |
25 |
| -
|
26 |
| - Example: |
27 |
| - Input: ring = "godding", key = "gd" |
28 |
| - Output: 4 |
29 |
| - Explanation: |
30 |
| - For the first key character 'g', since it is already in place, we just need 1 step to spell this character. |
31 |
| - For the second key character 'd', we need to rotate the ring "godding" anticlockwise by two steps to make it become "ddinggo". |
32 |
| - Also, we need 1 more step for spelling. |
33 |
| - So the final output is 4. |
34 |
| -
|
35 |
| - Note: |
36 |
| - Length of both ring and key will be in range 1 to 100. |
37 |
| - There are only lowercase letters in both strings and might be some duplcate characters in both strings. |
38 |
| - It's guaranteed that string key could always be spelled by rotating the string ring. |
39 |
| - */ |
40 | 3 | public class _514 {
|
41 | 4 |
|
42 | 5 | public static class Solution1 {
|
|
0 commit comments