514. Freedom Trail
今天又是Hard，這題應該也是dp
因為同一個字母可以出現多次，不同組合轉的次數會不同，要去找最小的次數
只要知道index就可以算出step，用一個hashtable去存每個字母的index
class Solution {
public:
int findRotateSteps(string ring, string key) {
int len = ring.size();
vector<vector<int>> v(26);
vector<int> steps(len);
for(int i = 0; i < ring.size(); i++){
v[ring[i] - 'a'].push_back(i);
}
char prev = key[0];
for(int i : v[key[0] - 'a']) {
steps[i] = min(i, len - i) + 1;
}
for(int n = 1; n < key.size(); n++){
for(int i : v[key[n] - 'a']){
int step = INT_MAX;
for(int j : v[prev - 'a']) {
step = min(step, steps[j] + min(abs(i - j), len - abs(i - j)
));
}
steps[i] = step + 1;
}
prev = key[n];
}
int ans = INT_MAX;
for(int i : v[prev - 'a']) {
ans = min(ans, steps[i]);
}
return ans;
}
};