../ Competitive Programming

-rw-r--r--aguang1.8 KiB2024-04-272 min read

Leet Code Daily 2024-04-27 - Freedom Trail

Description

Solution

First, let's say:

$M = len(\text{ring})$
$N = len(\text{key})$

DP

If we define:

$F(i, j) = \text{minimum steps to rotate from } \text{ring}_i \text{ to } \text{ring}_j$
$G(i, j) = \text{minimum steps to spell } \text{key}_{0..i} \text{ if } \text{key}_i \text{ is spelled by } \text{ring}_j$

Obviously,

F(i, j) = \min(\lvert i - j \rvert, M- \lvert i - j \rvert)

G(i, j)= \begin{cases} +\infty & \text{if } key_i \ne ring_j \\ 1 + F(0, j) & \text{if } key_i = ring_j \land i = 0 \\ 1 + \min_{0 \leq k \lt M}{ F(j, k) + G(i - 1, k) } & \text{if } key_i = ring_j \land i > 0 \end{cases}

And the answer should be $\min_{0 \leq i \lt M}F(N - 1, i)$ .

Code

c++

constexpr int kMaxSteps = 100 * 101;

class Solution {
public:
    int findRotateSteps(string ring, string key) {
        const int m = ring.size(), n = key.size();
        auto f = [&](int i, int j) {
            const int d = std::abs(i - j);
            return std::min(d, m - d);
        };
        int g[100][100];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                g[i][j] = kMaxSteps;
                if (key[i] != ring[j]) {
                    continue;
                }
                if (i == 0) {
                    g[i][j] = 1 + f(0, j);
                } else {
                    for (int k = 0; k < m; k++) {
                        g[i][j] = std::min(g[i][j], 1 + f(j, k) + g[i - 1][k]);
                    }
                }
            }
        }
        int ans = kMaxSteps;
        for (int i = 0; i < m; i++) {
            ans = std::min(ans, g[n - 1][i]);
        }
        return ans;
    }
};

press any key / click to skip