# C++ DP Solution

• O(key * ring * ring) time, O(ring) memory , 10ms

`dp[curr char] = min (dp[previous char] + distance between curr and prev char in ring)`

For example, `ring = "abcab"`, `key = "ba"`
For second char `'a'` in key, `'a'` indices in ring is `[0,3]`;
previous char of `'a'` is `'b'` in key, `'b'` indices in ring is `[1,4]`.
dp[0] = min( dp[1] + dist(0,1) , dp[4] + dist(0,4) );
dp[3] = min( dp[1] + dist(3,1) , dp[4] + dist(3,4) );

``````class Solution {
public:
int findRotateSteps(string ring, string key) {

vector<int> ring_idx[26]; //for each character in a-z, record the indices in ring
for(int i=0; i<ring.size(); i++)
ring_idx[ring[i]-'a'].push_back(i);

int rsize = ring.size();
vector<int> dp(rsize,0); //record the minimum step for each character on ring

for(int i=0; i<key.size(); i++)
{

vector<int> prev_idcs = (i>0) ? ring_idx[key[i-1]-'a'] : vector<int>(1,0); //previous char indices on the ring

for(int curr_idx : ring_idx[key[i]-'a']) //current char indices on the ring
{

int min_step = INT_MAX;

// for each current char on the ring, find the minimum step rotated from all the previous char indices
for(int prev_idx : prev_idcs)
min_step = min(min_step,dp[prev_idx]+dist(curr_idx,prev_idx,rsize));

//update the dp table
dp[curr_idx] = min_step;
}
}

int ans = INT_MAX;
for(int last_char_idx : ring_idx[key.back()-'a'])
ans = min(ans,dp[last_char_idx]);
return ans+key.size();
}

//return the minimum distance between two char indices
int dist(int i, int j, const int size){
int d = abs(i-j);
return min(d,size-d);
}
};
``````

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