c++ greedy&dp solution 12ms

• ``````class Solution {
public:
int findRotateSteps(string ring, string key) {
vector<pair<int,int>> v[26];
int l = ring.size();
//init first key char and dp
for(int i=0; i<l;i++){
if(ring[i]==key[0])
v[ring[i]-'a'].push_back({i,min(i,l-i)});
else
v[ring[i]-'a'].push_back({i,0});
}
//for each key[i], find the min distance for each key[i] in ring
for(int i= 1; i< key.size();i++){
if(key[i]==key[i-1]) continue;
int cur_c = key[i]-'a';
int pre_c = key[i-1]-'a';
for(int j=0;j<v[cur_c].size(); j++){
int dis = abs(v[cur_c][j].first - v[pre_c][0].first);
v[cur_c][j].second = v[pre_c][0].second + min(dis,l-dis);
for(int k=1; k<v[pre_c].size();k++){
dis = abs(v[cur_c][j].first - v[pre_c][k].first);
v[cur_c][j].second = min(v[cur_c][j].second, v[pre_c][k].second + min(dis,l-dis));
}
}
}

//minmum of last
int idx = key.back()-'a';
int min_dis=v[idx][0].second;
for(int i=1; i<v[idx].size();i++){
min_dis = min(min_dis, v[idx][i].second);
}
return min_dis+key.size();

}
};
``````

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.