Daily 27/04/2024: [514. Freedom Trail](https://leetcode.com/problems/freedom-trail/)

# 1. Tóm tắt đề bài
Trong trò chơi điện tử Fallout 4, nhiệm vụ "Road to Freedom" yêu cầu người chơi chạm tới một mặt số kim loại được gọi là "Vòng đường mòn tự do" và sử dụng mặt số để đánh vần một từ khóa cụ thể để mở cửa.

Cho một chuỗi ```ring``` đại diện cho mã được khắc ở vòng ngoài và một chuỗi khác ```key``` đại diện cho từ khóa cần đánh vần, trả về số bước tối thiểu để đánh vần tất cả các ký tự trong từ khóa .

Ban đầu, ký tự đầu tiên của vòng được căn chỉnh theo hướng ```"12:00"```. Bạn nên đánh vần từng ký tự ```key``` một bằng cách xoay ```ring``` theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ để mỗi ký tự của phím chuỗi căn chỉnh theo hướng ```"12:00"``` rồi nhấn nút giữa.

Đến công đoạn xoay vòng đánh vần ký tự chủ chốt ```key[i]```:

1. Bạn có thể xoay vòng theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ một vị trí, được tính là một bước . Mục đích cuối cùng của việc xoay là căn chỉnh một ```ring``` trong các ký tự của theo hướng ```"12:00"```, trong đó ký tự này phải bằng ```key[i]```.
2. Nếu ký tự ```key[i]``` đã được căn chỉnh theo hướng ```"12:00"``` thì nhấn nút giữa để đánh vần cũng được tính là một bước. Sau khi nhấn, bạn có thể bắt đầu đánh vần ký tự tiếp theo trong phím (giai đoạn tiếp theo). Nếu không, bạn đã hoàn thành tất cả chính tả.

#### Giới hạn
- $1 \le$ ```ring.length, key.length```$\le 300$
- ```ring``` và ```key``` chỉ bao gồm các chữ cái tiếng Anh viết thường.
- Nó được đảm bảo rằng ```key``` luôn có thể được đánh vần bằng cách xoay ```ring```.

# 2. Tóm tắt lời giải

#### Phân tích
- Đây là một bài Hard, tuy nhiên chúng ta nếu suy nghĩ chặt chẽ một chút thì hoàn toàn có thể giải quyết bài toán này bằng đệ quy có nhớ hoặc quy hoạch động.
- Trước hết thì khi chọn một chữ cái thì chúng ta có 2 cách xoay là xoay ngược hoặc xuôi kim đồng hồ thì chúng ta chỉ việc tính xem là mất bao nhiêu bước trong O(1).
- Vì giới hạn khá nhỏ ring.length, key.length < 100 nên ở bước đệ quy thì chúng ta xét tất cả chữ cái trong ```ring``` mà trùng với chữ cái hiện tại của ```key``` rồi tính .

# 3. Lời giải chi tiết
#### Thuật toán

#### Code

class Solution:
    def findRotateSteps(self, ring: str, key: str) -> int:
        n = len(ring)
        m = len(key)
        dp = {}

        # Tính xem xoay ngược hay xuôi ngon hơn :)
        def count_steps(curr, next):
            steps_between = abs(curr - next)
            steps_around = n - steps_between
            return min(steps_between, steps_around)

        def try_lock(ring_index, key_index, ):
            if key_index == m:
                return 0

            if (key_index, ring_index) in dp: return dp[(key_index, ring_index)] 

            min_steps = inf
            # Xét từng chữ cái trùng với chữ cái hiện tại với key để xoay
            for i in range(n):
                if ring[i] == key[key_index]:
                    total_steps = count_steps(ring_index, i) + 1 + try_lock(i, key_index + 1)
                    min_steps = min(min_steps, total_steps)

            dp[(key_index, ring_index)] = min_steps
            return min_steps
    
        return try_lock(0, 0)
        

#### Độ phức tạp
$O(n \cdot m)$

# 4. Kết luận & gợi ý mở rộng
- Một bài cuối tuần khá không nhẹ nhàng.

> Hãy dùng nghị lực và sự kiên trì để đánh bại mọi thứ.

###### #Hashtag: <span style='color: blue'>Stack</span>