514. 自由之路

514. 自由之路

dp

看的官方题解。。

class Solution {
public:
    int findRotateSteps(string ring, string key) {
        int n = ring.size(), m = key.size();
        vector<int> pos[26];
        for (int i = 0; i < n; i++) {
            pos[ring[i] - 'a'].push_back(i);
        }
        int dp[m][n];
        memset(dp, 0x3f3f3f3f, sizeof dp);

        for (auto j:pos[key[0] - 'a']) {
            dp[0][j] = min(dp[0][j], min(j, (n - j)) + 1);
        }

        for (int i = 1; i < m; i++) {
            for (auto j:pos[key[i] - 'a']) {
                for (auto k:pos[key[i - 1] - 'a']) {
                    dp[i][j] = min(dp[i][j], dp[i - 1][k] + min((j - k + n) % n, (k - j + n) % n) + 1);
                }
            }
        }
        int res = 0x3f3f3f3f;
        for (int i = 0; i < n; i++)res = min(res, dp[m - 1][i]);
        return res;
    }
};