Description
In the video game Fallout 4, the quest “Road to Freedom” requires players to reach a metal dial called the “Freedom Trail Ring”, and use the dial to spell a specific keyword in order to open the door.
Given a string ring, which represents the code engraved on the outer ring and another string key, which represents the keyword needs to be spelled. You need to find the minimum number of steps in order to spell all the characters in the keyword.
Initially, the first character of the ring is aligned at 12:00 direction. You need to spell all the characters in the string key one by one by rotating the ring clockwise or anticlockwise to make each character of the string key aligned at 12:00 direction and then by pressing the center button.At the stage of rotating the ring to spell the key character key[i]:
- You can rotate the ring clockwise or anticlockwise one place, which counts as 1 step. The final purpose of the rotation is to align one of the string ring’s characters at the 12:00 direction, where this character must equal to the character key[i].
- If the character key[i] has been aligned at the 12:00 direction, you need to press the center button to spell, which also counts as 1 step. After the pressing, you could begin to spell the next character in the key (next stage), otherwise, you’ve finished all the spelling.
Input: ring = “godding”, key = “gd” Output: 4 Explanation: For the first key character ‘g’, since it is already in place, we just need 1 step to spell this character. For the second key character ‘d’, we need to rotate the ring “godding” anticlockwise by two steps to make it become “ddinggo”. Also, we need 1 more step for spelling. So the final output is 4.
Note
- Length of both ring and key will be in range 1 to 100.
- There are only lowercase letters in both strings and might be some duplcate characters in both strings.
- It’s guaranteed that string key could always be spelled by rotating the string ring.
方法描述
由于做出来的时候posted在discuss了,所以我直接复制里面的内容
- 看Tag上dp上打了个冒号,这似乎不完全算是一个dp solution
- 基本思路:
- 对于解一个key,我们可以将这个key的长度作为我们接这道题的step,每一步step接一个char,解到最后一个字符最小step就是我们需要求的答案
- 所以算法开始,我们需要知道,key对应的每一个char在string ring中的哪一个位置,需要对ring for一遍,将对应的char记录在相应的mp中,这样可以节省很多的搜索时间。
- 开始搜索key的循环,算法第一步开始的index为 ring[0],需要求转动ring,使达到ring[index]==key[0](第一步)的步数最小,因为可能ring中不止有一个key[0],所以需要对每一个符合的进行选择,(每一个dp[i][j],记录的实际就是在第i步时,通过起点到达j的最短step,主要是考虑rotate left or right)
- 依次循环key.size()步后结束循环
- 对最后一个dp数组for出最小的值,return minStep + key.size()即是最小的步数
Simple dp idea
- recording each index of characters in ring,beacuse each characters we have search in this time would be starting index in the next search
- 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 it ‘s 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 :)
实现代码与optimazed
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;
}
};