# Shared my C++ dp solution ,19ms

• Simple dp idea

1. recording each index of characters in ring,beacuse each characters we have search in this time would be starting index in the next search
2. How could we solve the problem that rotate the ring to the left or right ? My idea is min((tmp[j] + size -it)%size,(it + size - tmp[j])%size)
• Suppose you want to rotate the ring to the right and search 'k', and the size is 5.
We could calculate it by this + size -k(index)%size
this -  -  -  -  k

• If we want to rotate the ring to the left，what should we do? It is the same problem with above problem,move this to its right,and reach k
k -  -  -  -   this

• So we could calculate it by k(index) + size -this%size
• There are many people use abs() instead of %size,I think it's faster than mine :)
class Solution {
public:
int findRotateSteps(string ring, string key) {
int size = ring.size();
int ksize = key.size();
unordered_map<char,vector<int>> mp;//stored index of each characters in ring,pay attention to duplcate characters.
for(int i=0;i<size;++i){
mp[ring[i]].push_back(i);
}

vector<vector<int>> dp(ksize+1,vector<int> (size,INT_MAX));// initializing dp vector
fill(dp[0].begin(),dp[0].end(),0);

vector<int> tmp(1,0);// starting index

int res = INT_MAX;
for(int i=1;i<=ksize;++i){
for(auto it:mp[key[i-1]]){  //
for(int j=0;j<tmp.size();++j){  //Search The shortest distance key[i-1] in ring
int minDist = min((tmp[j] + size -it)%size,(it + size - tmp[j])%size) + dp[i-1][tmp[j]];// Look at the above explanation
dp[i][it] =min(dp[i][it],minDist);
res = (i!=ksize?res:min(res,dp[i][it])); //Can we optimize it?
}
}
tmp = mp[key[i-1]]; //next start is the characters we search in this time
}
return res + ksize;
}
};

update (optimazed space complexity)

class Solution {
public:
int findRotateSteps(string ring, string key) {
int size = ring.size();
int ksize = key.size();
vector<vector<int>> mp(26);   //Optimazed_1 use vector instead of unordered_map
//stored index of each ,pay attention to duplcate characters.
for(int i=0;i<size;++i){
mp[ring[i]-'a'].push_back(i);
}

vector<int> dp (size,INT_MAX);   //Optimazed_2,use less space
dp[0] = 0;

vector<int> startIndex(1,0);// starting index

for(int i=1;i<=ksize;++i){
vector<int> nextDp(size,INT_MAX);
for(auto it:mp[key[i-1]-'a']){
for(int j=0;j<startIndex.size();++j){
int minDist = min((startIndex[j] + size -it)%size,(it + size - startIndex[j])%size) + dp[startIndex[j]];// Look at the above explanation
nextDp[it] =min(nextDp[it],minDist);
}
}
startIndex = mp[key[i-1]-'a'];
dp = nextDp;
}

int res = INT_MAX;
for(int i=0;i<size;++i){
res = min(res,dp[i]);
}  // get the smallest value(step)

return res + ksize;
}
};

• clear and easy understanding solution!

• Can you explain why the startIndex is initialized as [1, 0] ?

• @0x0101
Firstly , startIndex = [0] not [1,0]
There is the vector constructor

vector (size_type n, const value_type& val,const allocator_type& alloc = allocator_type());
(just understand this )
vector (size_type n, const value_type& val...);

So vector<int> (1,0) just 1 elements(0) in the container = {0};

Secondly,We begin at the first elements in rings , it mean we start searching from index 0

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