# C++_DP_Space: O(n), Time: O(r*r*k)

• ``````class Solution {
public:
int findRotateSteps(string ring, string key) {
unordered_map<int,vector<int>> mp;
for(int i = 0; i < ring.size(); ++i){
mp[ring[i]].push_back(i);
}
int n = ring.size();
int m = key.size();
int r_len = ring.size();
vector<int> dp(n, INT_MAX);
for(auto j : mp[key[0]]){
dp[j] = min(j, r_len - j);
}
//dp[j]：the minimized steps needed from start to j where j is the current position at Ring,  if our current position in Key is k.
int res = INT_MAX;
for(int k = 1; k < m; ++k){
vector<int> tmp(n, INT_MAX);
vector<int> curPos = mp[key[k]];//The positions we need to calculate for current position at k in Key.
for(auto cur : curPos){
for(int j = 0; j < n; ++j){
if(dp[j] < INT_MAX){
tmp[cur] = min(tmp[cur], dp[j] + min(abs(cur - j), r_len - abs(cur - j)));
}
}
}
dp = tmp;
}
for(auto num : dp){
res = min(res, num);
}
return res + key.size();
}
};``````

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