Re: [闲聊] 每日leetcode

楼主: ray90514 (读书人)   2024-04-27 13:05:44
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;
}
};

Links booklink

Contact Us: admin [ a t ] ucptt.com