LeetCode 514. 自由之路
原题链接
困难
class Solution {
public:
int findRotateSteps(string ring, string key) {
int n = ring.size(), m = key.size();
ring = ' ' + ring;
key = ' ' + key;
vector<vector<int>> f(m + 1, vector<int>(n + 1, 1e8));
f[0][1] = 0;
for(int i = 1; i <= m; i ++) {
for(int j = 1; j <= n; j ++) {
if(ring[j] == key[i]) {
for(int k = 1; k <= n; k ++) {
int t = abs(j - k);
f[i][j] = min(f[i][j], f[i - 1][k] + min(t, n - t) + 1);
}
}
}
}
int result = INT_MAX;
for(int i = 1; i <= n; i ++) result = min(result, f[m][i]);
return result;
}
};