514. Freedom Trail
Tags: programming, php, leetcode, algorithms
Published: 2024-04-27 18:02:07

514\. Freedom Trail

Hard

In the video game Fallout 4, the quest **"Road to Freedom"** requires players to reach a metal dial called the **"Freedom Trail Ring"** and use the dial to spell a specific keyword to open the door.

Given a string `ring` that represents the code engraved on the outer ring and another string `key` that represents the keyword that needs to be spelled, return _the minimum number of steps to spell all the characters in the keyword_.

Initially, the first character of the ring is aligned at the `"12:00"` direction. You should spell all the characters in `key` one by one by rotating `ring` clockwise or anticlockwise to make each character of the string key aligned at the `"12:00"` direction and then by pressing the center button.

At the stage of rotating the ring to spell the key character `key[i]`:

1. You can rotate the ring clockwise or anticlockwise by one place, which counts as **one step**. The final purpose of the rotation is to align one of `ring`'s characters at the `"12:00"` direction, where this character must equal `key[i]`. 
2. If the character `key[i]` has been aligned at the `"12:00"` direction, press the center button to spell, which also counts as **one step**. After the pressing, you could begin to spell the next character in the key (next stage). Otherwise, you have finished all the spelling.


**Example 1:**

![ring](https://assets.leetcode.com/uploads/2018/10/22/ring.jpg)

- **Input:** ring = "godding", key = "gd"
- **Output:** 4
- **Explanation:** 
```
For the first key character 'g', since it is already in place, we just need 1 step to spell this character.
For the second key character 'd', we need to rotate the ring "godding" anticlockwise by two steps to make it become "ddinggo".
Also, we need 1 more step for spelling.
So the final output is 4.
```

**Example 2:**

- **Input:** ring = "godding", key = "godding"
- **Output:** 13


**Constraints:**

- `1 <= ring.length, key.length <= 100`.
- `ring` and `key` consist of only lower case English letters.
- It is guaranteed that `key` could always be spelled by rotating `ring`.

**Solution:**

```
class Solution {

    /**
     * @param String $ring
     * @param String $key
     * @return Integer
     */
    function findRotateSteps($ring, $key) {
        $len_key = strlen($key);
        $len_ring = strlen($ring);
        $char_positions = array();
        
        for($index = 0; $index < $len_ring; $index++) {
            $char = $ring[$index];
            $char_positions[$char][] = $index;
        }
        
        $dp = array_fill(0, $len_key, array_fill(0, $len_ring, INF));
        
        foreach($char_positions[$key[0]] as $j) {
            $dp[0][$j] = min($j, $len_ring - $j) + 1;
        }
        
        for($i = 1; $i < $len_key; $i++) {
            foreach($char_positions[$key[$i]] as $j) {
                foreach($char_positions[$key[$i - 1]] as $k) {
                    $dp[$i][$j] = min($dp[$i][$j], $dp[$i - 1][$k] + min(abs($j - $k), $len_ring - abs($j - $k)) + 1);
                }
            }
        }
        
        $min_steps = INF;
        
        foreach($char_positions[$key[$len_key - 1]] as $j) {
            $min_steps = min($min_steps, $dp[$len_key - 1][$j]);
        }
        
        return $min_steps;
    }
}
```


**Contact Links**

- **[LinkedIn](https://www.linkedin.com/in/arifulhaque/)**
- **[GitHub](https://github.com/mah-shamim)**