LeetCode 514 Freedom Trail
概述
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