LeetCode 514 Freedom Trail

标签: 动态规划问题 LeetCode 发布于:2022-02-19 17:30:51 编辑于:2022-02-19 17:35:01 浏览量:1104

概述

https://leetcode.com/problems/freedom-trail/

动态规划法

139 / 303 test cases passed:

class Solution {
public:
    unordered_map<char, vector<int>> char2idx;
    string ring;
    string key;
    vector<vector<int>> dp;
    int findRotateSteps(string ring, string key) {
        for (int i = 0; i < ring.size(); i ++) char2idx[ring[i]].push_back(i);
        this->ring = ring;
        this->key = key;
        vector<vector<int>> dp(ring.size(), vector<int>(key.size(), -1));
        this->dp = dp;
        return helper(0, 0);
    }
    
    int helper(int i, int j) {  // i is the idx for ring, j is the idx for key
        if (dp[i][j] != -1) return dp[i][j];
        int c = 1;
        if (j + 1 == key.size()) return c;
        int restc = INT_MAX;
        for (auto nexti : char2idx[key[j+1]]) {
            int mini = i > nexti ? nexti : i;
            int maxi = i < nexti ? nexti : i;
            int cost = min(maxi - mini, mini + int(ring.size()) - maxi);
            restc = min(restc, cost + helper(nexti, j + 1));
        }
        dp[i][j] = c + restc;
        return dp[i][j];
    }
};

佛了,读错题意了,我以为第一个字符永远已经搞定了呢。

还好要改的不多,不然我直接裂开:

class Solution {
public:
    unordered_map<char, vector<int>> char2idx;
    string ring;
    string key;
    vector<vector<int>> dp;
    int findRotateSteps(string ring, string key) {
        for (int i = 0; i < ring.size(); i ++) char2idx[ring[i]].push_back(i);
        this->ring = ring;
        this->key = key;
        vector<vector<int>> dp(ring.size(), vector<int>(key.size(), -1));
        this->dp = dp;
        return helper(0, 0);
    }
    
    int helper(int i, int j) {  // i is the idx for ring, j is the idx for key
        if (j == key.size()) return 0;
        if (dp[i][j] != -1) return dp[i][j];
        int c = 1;
        int restc = INT_MAX;
        for (auto nexti : char2idx[key[j]]) {
            int mini = i > nexti ? nexti : i;
            int maxi = i < nexti ? nexti : i;
            int cost = min(maxi - mini, mini + int(ring.size()) - maxi);
            restc = min(restc, cost + helper(nexti, j + 1));
        }
        dp[i][j] = c + restc;
        return dp[i][j];
    }
};

说一点,其实由顺时针的结果可以推出逆时针的结果的:

// 拨动指针的次数
int delta = abs(k - i);
// 选择顺时针还是逆时针
delta = min(delta, n - delta);

未经允许,禁止转载,本文源站链接:https://iamazing.cn/