LeetCode 514 Freedom Trail

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

概述

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);

Links: leetcode-514-freedom-trail