Solution:
Basically, there are two ways to switch into the target position. One is to from left to right; the other is the opposite direction. And we need to pick up the shorter one to continue. The difficult part is that there are duplicates in both the ring and key, so we need to try each of them, so we can use brute force DSF and then return the one with the shortest length. To reduce the time complexity, a hash map can be used to built up the relationship between the char in the key and the corresponding positions in the ring. See code below, (even though it is still too slow to pass the OJ)
Code:
class Solution {
public:
int findRotateSteps(string ring, string key) {
int m=ring.size(), n=key.size();
if(!m || !n) return 0;
int res = m*n;
unordered_map<int, vector<int>> map;
for(auto a: key){
if(map.find(a-'a') == map.end()){
for(int i=0; i<m; ++i){
if(ring[i]==a) map[a-'a'].push_back(i);
}
}
}
findDSF(ring, 0, key, 0, 0, map, res);
return res;
}
private:
void findDSF(string r, int i, string key, int j, int l, unordered_map<int, vector<int>> &m, int &res){
if(l>=res) return;
if(j==key.size()){res = l; return;}
for(auto k:m[key[j]-'a']){
int t1 = abs(k-i), t = r.size(), t2 = t - t1;
findDSF(r, k, key, j+1, l+min(t1, t2)+1, m, res);
}
}
};
Since the above brute force DSF cannot pass the OJ, we need to think about something else that is faster. DP is one choice. Let's use dp[i][j] represent the shortest length to match key [0, to i] and ring[0-j]. When key[i] == ring[j],
dp[i][j] = min(dp[i-1][k] + min steps from k to j) for all k (0<= k < ring.size())The min steps from k to j can be obtained by comparing the two way mentioned above: one is from left to right; the other is the opposite way. And we need to choose the shorter one.
Some details for initialization:
1): the maximum steps will be the length of ring times the length of the key; (why? because this is the worst case: for every char in the key, we need to search the whole ring);
2): We can initialize the dp[i][j] with the maximum steps, since we are looking for minimum;
3): dp[0][0] can be set as 0, which is legal for empty ring and empty key.
Code:
class Solution {
public:
int findRotateSteps(string ring, string key) {
int m=ring.size(), n=key.size();
if(!m || !n) return 0;
int res = m*n;
vector<vector<int>> dp(n+1, vector<int>(m, res));
dp[0][0] = 0;
for(int i=1; i<=n; ++i){
for(int j=0; j<m; ++j){
if(ring[j]==key[i-1]){
for(int k=0; k<m; ++k){
int t1 = abs(k-j), t2 = m-t1;//two ways from k to j;
dp[i][j]=min(dp[i][j], dp[i-1][k] + min(t1, t2) + 1); //+1 for the "click" step;
if(i==n) res = min(res, dp[i][j]);
}
}
}
}
return res;
}
};
