http://blog.jerkybible.com/2017/03/18/LeetCode-514-Freedom-Trail/
这道题讲的是一种叫做自由之路的机关，我们需要将密码字符串都转出来，让我们求最短的转动步数。博主最先尝试的用贪婪算法来做，就是每一步都选最短的转法，但是OJ中总有些test case会引诱贪婪算法得出错误的结果，因为全局最优解不一定都是局部最优解，而贪婪算法一直都是在累加局部最优解，这也是为啥DP解法这么叼的原因。贪婪算法好想好实现，但是不一定能得到正确的结果。DP解法难想不好写，但往往才是正确的解法，这也算一个trade off吧。这道题可以用DP来解，难点还是写递推公式，博主在充分研究网上大神们的帖子后尝试着自己理理思路，如果有不正确或者不足的地方，也请各位不吝赐教。
此题需要使用一个二维数组dp，其中dp[i][j]表示转动从i位置开始的key串所需要的最少步数(这里不包括spell的步数，因为spell可以在最后统一加上)，此时表盘的12点位置是ring中的第j个字符。不得不佩服这样的设计的确很巧妙，我们可以从key的末尾往前推，这样dp[0][0]就是我们所需要的结果，因为此时是从key的开头开始转动，而且表盘此时的12点位置也是ring的第一个字符。现在我们来看如何找出递推公式，对于dp[i][j]，我们知道此时要将key[i]转动到12点的位置，而此时表盘的12点位置是ring[j]，我们有两种旋转的方式，顺时针和逆时针，我们的目标肯定是要求最小的转动步数，而顺时针和逆时针的转动次数之和刚好为ring的长度n，这样我们求出来一个方向的次数，就可以迅速得到反方向的转动次数。为了将此时表盘上12点位置上的ring[j]转动到key[i]，我们要将表盘转动一整圈，当转到key[i]的位置时，我们计算出转动步数diff，然后计算出反向转动步数，并取二者较小值为整个转动步数step，此时我们更新dp[i][j]，更新对比值为step + dp[i+1][k]，这个也不难理解，因为key的前一个字符key[i+1]的转动情况suppose已经计算好了，那么dp[i+1][k]就是当时表盘12点位置上ring[k]的情况的最短步数，step就是从ring[k]转到ring[j]的步数，也就是key[i]转到ring[j]的步数，用语言来描述就是，从key的i位置开始转动并且此时表盘12点位置为ring[j]的最小步数(dp[i][j])就等价于将ring[k]转动到12点位置的步数(step)加上从key的i+1位置开始转动并且ring[k]已经在表盘12点位置上的最小步数(dp[i+1][k])之和。突然发现这不就是之前那道Reverse Pairs中解法一中归纳的顺序重现关系的思路吗，都做了总结，可换个马甲就又不认识了，泪目中
X. DFS + cache
- the fastest submission
public int findRotateSteps(String ring, String key) { if (ring == null) return 0; List<Integer>[] r = new List[26]; for (int i = 0; i < 26; i++) { r[i] = new ArrayList<Integer>(); } for (int i = 0; i < ring.length(); i++) { r[ring.charAt(i) - 'a'].add(i); } int[][] cache = new int[ring.length()][key.length()]; return search(r, ring.length(), 0, key, 0, cache); } private int search(List<Integer>[] ring, int len, int p, String key, int index, int[][] cache) { if (index == key.length()) return 0; if (cache[p][index] > 0) return cache[p][index]; char c = key.charAt(index); List<Integer> indices = ring[c - 'a']; int min = Integer.MAX_VALUE; for (int i: indices) { int oneDir = Math.abs(p - i); int otherDir = len - oneDir; min = Math.min(min, 1 + Math.min(oneDir, otherDir) + search(ring, len, i, key, index + 1, cache)); } cache[p][index] = min; return min; }
https://leetcode.com/problems/freedom-trail/discuss/98953/JAVA-DP-with-explanation
The dp is a 2D integer array, with height = the length of ring, with width = the length of key. So DP[i][j] represents that if we want to spell the next character key[j], and at the same time the 12:00 aligns with the ring[i], then what is the minimum steps to spell the whole key start at key[j]. If we finish the DP array, then the answer is just DP[0][0], which means the minimum steps to spell the whole key start at key[0], if currently 12:00 aligns with the ring[0], and this is exactly the original problem. And don't forget to plus the length of key, which is the steps we need to push the button.
http://www.cnblogs.com/grandyang/p/6675879.html
下面这种解法是用DFS来解的，我们需要做优化，也就是用memo数组来保存已经计算过的结果，否则大量的重复运算是无法通过OJ的。其实这里的memo数组也起到了跟上面解法中的dp数组相类似的作用，还有就是要注意数组v的作用，记录了每个字母在ring中的出现位置，由于ring中可能有重复字符，而且麻烦的情况是当前位置向两个方向分别转动相同的步数会分别到达两个相同的字符，这也是贪婪算法会失效的一个重要原因，而且也是上面的解法在找到ring[k] == key[i]并处理完之后不break的原因，因为后面还有可能找到。上面的迭代解法中使用到的变量i和j可以直接访问到，而在递归的写法中必须要把位置变量x和y当作参数导入进去，这样才能更新正确的地方
可以发现，打完 y，再打 n 时，发现顺时针和逆时针都可以到n。选哪个呢？这时候需要根据之后的字母离得跟哪个n比较近来抉择。
因此 当前的选择 需要根据之后的情况来选择 min step 的情况，要用递归来做。使用纯递归会TLE，因此使用递归with memory。
主要的问题是决定 是顺时针转还是逆时针转。在 brute force , 对于每个需要打出来的字符有两种选择：
顺时针来搜索这个字符
逆时针来搜索这个字符
为了得到最优解，我们需要都尝试这两种情况，并且选择这两种情况中的 min steps。对于一些位置可能会有重复计算的情况，因此我们需要存储 states 。state 由两者定义：ring 中被作为12点的位置， key 中字符的索引。使用map来存储state ，避免相同的 state 被重复计算。map的key是 ring中12点位置的索引，value是<key中的索引 , 从key中的索引开始打出字符串需要的最少步骤>。
在代码的方法参数中，index是当前所需要打的字符的index，position_12是当前位于12点位置的字母在cs[]中的索引。
题目来自于辐射4这个游戏。有一个圆盘，圆盘上有几个英文字母，圆盘12点方向代表当前选中的字母，通过这个圆盘拼出一个和题目一样的字符串，求出最小的步数。
X. brute force, try all next steps.
https://discuss.leetcode.com/topic/82720/evolve-from-brute-force-to-dp
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.
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.
Example:
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.
题目来自于辐射4这个游戏。有一个圆盘，圆盘上有几个英文字母，圆盘12点方向代表当前选中的字母，通过这个圆盘拼出一个和题目一样的字符串，求出最小的步数。
圆盘可以顺时针或者逆时针旋转，每旋转一个字母代表1步，当12点方向是需要的英文字母时，按确定按钮，这个按也算一步。
https://www.jianshu.com/p/65f633026a82- 画DP的表格，用一个例子推倒一遍过程，发现程序逻辑规律。
- 写dp表格格式，分析是2D还是1D，用Boolean[][]还是int[][], 学会用int替代String。
- 循环，可以从后往前循环比较直观对应子问题。
- 记得初始化dp[i][j]，Integer.MAX_VALUE or 1 or true.
- 注意比较条件，递推方程怎么依附于子问题。
- 可以打印出dp debug。
- 注意返回值是否符合要求。
- 注意边界情况，array==null or length==0
注意的点
- 不论从后往前还是从前往后，都要预留出一行
这道题讲的是一种叫做自由之路的机关，我们需要将密码字符串都转出来，让我们求最短的转动步数。博主最先尝试的用贪婪算法来做，就是每一步都选最短的转法，但是OJ中总有些test case会引诱贪婪算法得出错误的结果，因为全局最优解不一定都是局部最优解，而贪婪算法一直都是在累加局部最优解，这也是为啥DP解法这么叼的原因。贪婪算法好想好实现，但是不一定能得到正确的结果。DP解法难想不好写，但往往才是正确的解法，这也算一个trade off吧。这道题可以用DP来解，难点还是写递推公式，博主在充分研究网上大神们的帖子后尝试着自己理理思路，如果有不正确或者不足的地方，也请各位不吝赐教。
此题需要使用一个二维数组dp，其中dp[i][j]表示转动从i位置开始的key串所需要的最少步数(这里不包括spell的步数，因为spell可以在最后统一加上)，此时表盘的12点位置是ring中的第j个字符。不得不佩服这样的设计的确很巧妙，我们可以从key的末尾往前推，这样dp[0][0]就是我们所需要的结果，因为此时是从key的开头开始转动，而且表盘此时的12点位置也是ring的第一个字符。现在我们来看如何找出递推公式，对于dp[i][j]，我们知道此时要将key[i]转动到12点的位置，而此时表盘的12点位置是ring[j]，我们有两种旋转的方式，顺时针和逆时针，我们的目标肯定是要求最小的转动步数，而顺时针和逆时针的转动次数之和刚好为ring的长度n，这样我们求出来一个方向的次数，就可以迅速得到反方向的转动次数。为了将此时表盘上12点位置上的ring[j]转动到key[i]，我们要将表盘转动一整圈，当转到key[i]的位置时，我们计算出转动步数diff，然后计算出反向转动步数，并取二者较小值为整个转动步数step，此时我们更新dp[i][j]，更新对比值为step + dp[i+1][k]，这个也不难理解，因为key的前一个字符key[i+1]的转动情况suppose已经计算好了，那么dp[i+1][k]就是当时表盘12点位置上ring[k]的情况的最短步数，step就是从ring[k]转到ring[j]的步数，也就是key[i]转到ring[j]的步数，用语言来描述就是，从key的i位置开始转动并且此时表盘12点位置为ring[j]的最小步数(dp[i][j])就等价于将ring[k]转动到12点位置的步数(step)加上从key的i+1位置开始转动并且ring[k]已经在表盘12点位置上的最小步数(dp[i+1][k])之和。突然发现这不就是之前那道Reverse Pairs中解法一中归纳的顺序重现关系的思路吗，都做了总结，可换个马甲就又不认识了，泪目中
X. DP
动态规划的解法是，初始化二维数组
dp[i][j]，height为key的长度，width为ring的长度。dp[i][j]表示key是从i开始的子字符串和ring从ring[j]开始时的最小解题步数。dp[i][j] = Math.min(dp[i][j], step + dp[i + 1][k])，其中step表示从ring[j]开始旋转得到第ring[k]的最小步数，k表示key[i]=ring[k];public int findRotateSteps(String ring, String key) {int n = ring.length();int m = key.length();int[][] dp = new int[m + 1][n];for (int i = m - 1; i >= 0; i--) {for (int j = 0; j < n; j++) {dp[i][j] = Integer.MAX_VALUE;for (int k = 0; k < n; k++) {if (ring.charAt(k) == key.charAt(i)) {int diff = Math.abs(j - k);int step = Math.min(diff, n - diff);dp[i][j] = Math.min(dp[i][j], step + dp[i + 1][k]);}}}}return dp[0][0] + m;}
The time complexity O(mn) is implemented by greedy choice, which is "The optimal answer can always be achieved by rotating clockwise or anti-clockwise to the next identical character". If there is an optimal solution by rotating clockwise to the kth identical character, we can get equally optimal solution by rotating clockwise to the first identical one, pressing it, and continuing rotating to the kth one.
For example,
key = "abc", ring = "ddaddabcdddda";
The optimal solution is to rotate anti-clockwise by 5 steps. But you can also rotate anti-clockwise by 2 step, press it, and rotate another 3 steps.
public int findRotateSteps(String ring, String key) {
int n = ring.length();
int m = key.length();
int[][] dp = new int[m + 1][n];
for (int i = m - 1; i >= 0; i--) {
for (int j = 0; j < n; j++) {
dp[i][j] = Integer.MAX_VALUE;
for (int k = 0; k < n; k++) {
if (ring.charAt(k) == key.charAt(i)) {
int diff = Math.abs(j - k);
int step = Math.min(diff, n - diff);
dp[i][j] = Math.min(dp[i][j], step + dp[i + 1][k]);
}
}
}
}
return dp[0][0] + m;
}
X. DP 2
* O(n^3) DP
* f[i][j]: min total distance when correctly typed the first i letters in key and stopped at j-th position of the ring.
* <p>
* 1) Many states are illegal, but that is okay.
* 2) We can in fact compute f[i][j] in O(1) time, see the improved version.
public int findRotateSteps(String ring, String key) {
if (key.length() == 0)
return 0;
int ans = Integer.MAX_VALUE;
int[][] f = new int[key.length() + 1][ring.length()];
Arrays.fill(f[0], Integer.MAX_VALUE / 2);
f[0][0] = 0;
for (int i = 1; i < f.length; i++) { // Index-i is shifted by 1.
for (int j = 0; j < ring.length(); j++) {
f[i][j] = Integer.MAX_VALUE / 2;
if (ring.charAt(j) == key.charAt(i - 1)) {
for (int k = 0; k < ring.length(); k++) {
f[i][j] = Math.min(f[i][j], f[i - 1][k] + Math.min(Math.abs(j - k), ring.length() - Math.abs(j - k)));
}
}
if (i == key.length())
ans = Math.min(ans, f[i][j]);
}
}
return ans + key.length();
}
public int findRotateSteps(String ring, String key) {
int n = ring.length();
int m = key.length();
int[][] dp = new int[m + 1][n];
for (int i = 1; i < m + 1; i++) {
for (int j = 0; j < n; j++) {
dp[i][j] = Integer.MAX_VALUE;
for (int k = 0; k < n; k++) {
if (ring.charAt(k) == key.charAt(m - i)) {
int diff = Math.abs(j - k);
int step = Math.min(diff, n - diff);
dp[i][j] = Math.min(dp[i][j], step + dp[i - 1][k]);
}
}
}
}
return dp[m][0] + m;
}
路径搜索问题，或者字符串匹配问题，可以正向或者逆向匹配。
动态规划记录当前的状态result[i][j]，即当前匹配到key的第i个字母，ring的第j个字母在12点方向，要匹配key的下一个字母时，可以从上一个状态顺时针或者逆时针转移到现在的状态。
动态规划记录当前的状态result[i][j]，即当前匹配到key的第i个字母，ring的第j个字母在12点方向，要匹配key的下一个字母时，可以从上一个状态顺时针或者逆时针转移到现在的状态。
public int findRotateSteps(String ring, String key) {
if (ring == null || key == null)
return 0;
int m = ring.length();
int n = key.length();
int[][] result = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
result[i][j] = Integer.MAX_VALUE;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (key.charAt(i) == ring.charAt(j)) {
if (i == 0) {
result[i][j] = Math.min(j, m - j);// first char
} else {
for (int k = 0; k < m; k++) {
if (result[i - 1][k] != Integer.MAX_VALUE)
result[i][j] = Math.min(result[i][j],
result[i - 1][k] + Math.min(Math.abs(j - k), m - Math.abs(j - k)));
// it can ring clockwise or anticlockwise from k to j
}
}
}
}
}
int ans = result[n - 1][0];
for (int j = 1; j < m; j++) {
if (ans > result[n - 1][j])
ans = result[n - 1][j];
}
return ans + n;
}
通过匹配的方法，从key中一一取出一个字符，在ring中匹配，得到转到该字符的最小转数。注意，除了第一个字符外，剩下的字符的转数需要由上一个字符的转数加上转动次数决定。本题需要考虑的是当出现了顺、逆时针转动时都有相同转数的匹配，这是应该选择顺时针还是逆时针，这里需要将两种结果与下一个匹配的结果相加进行比较来选择。dp[i][j]表示key的从0到i的字符匹配到ring的j字符需要的最小的step
LeetCode做得比较多了就很容易发现一个规律，就是LeetCode所能接受的最大总时间复杂度大约在
10^6左右，根据观察输入数据的规模就能大致的知道所用算法的时间复杂度上限是多少。比如输入数据是10000或以上，那么O(n^2)一般就是TLE（除非大量剪枝有可能勉强能过），如果输入数据是1000，那么O(n^2)就是可接受的。这道题的输入数据规模只有100，所以O(n^3)的算法也是可以的，我用的DP就是三次方的复杂度。
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.
- 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;
- }
X. DP 3 Best
We can further improve the runtime of this DP Solution from
O(R * R * K) to O(R * (26 + K)) = O(RK), where R = |Ring| and K = |Key|. Basically, we can do the inner-most loop in O(1) time. The idea is that if we are currently at position i and require the previous char equal to some letter ch, we just need to check the position (with letter ch) that is closest to i from its left or right. Thus, at most two positions need to be checked, instead of the entire ring.
Update: The preprocessing of the following code takes I was just too lazy to do that...
Update: Okay, the preprocessing can be done in
O(R^2 * 26) = O(R^2) time. But I believe there must exist a faster way, and Update: Okay, the preprocessing can be done in
O(26 * R) = O(R) time.public int findRotateSteps(String ring, String key) {
int R = ring.length(), K = key.length();
int[][] prev = new int[R][26], next = new int[R][26];
for (int i = 0; i < R; i++) {
Arrays.fill(prev[i], -1);
Arrays.fill(next[i], -1);
for (int j = (i + 1) % R; j != i; j = (j + 1) % R) {
int ch = ring.charAt(j) - 'a';
if (next[i][ch] == -1) next[i][ch] = j;
}
for (int j = (i - 1 + R) % R; j != i; j = (j - 1 + R) % R) {
int ch = ring.charAt(j) - 'a';
if (prev[i][ch] == -1) prev[i][ch] = j;
}
prev[i][ring.charAt(i) - 'a'] = next[i][ring.charAt(i) - 'a'] = i;
}
int[][] f = new int[K][R];
int ans = Integer.MAX_VALUE;
for (int i = 0; i < K; i++) {
for (int j = 0; j < R; j++) {
f[i][j] = Integer.MAX_VALUE / 2;
if (key.charAt(i) == ring.charAt(j)) {
if (i == 0) f[i][j] = Math.min(f[i][j], dist(0, j, ring.length()));
else {
int preKey = key.charAt(i - 1) - 'a';
f[i][j] = Math.min(f[i][j], f[i - 1][prev[j][preKey]] + dist(prev[j][preKey], j, ring.length()));
f[i][j] = Math.min(f[i][j], f[i - 1][next[j][preKey]] + dist(next[j][preKey], j, ring.length()));
}
}
if (i == K - 1) ans = Math.min(ans, f[i][j]);
}
}
return ans + K;
}
An
O(26R) = O(R)-time preprocessing.int R = ring.length(), K = key.length();
int[][] prev = new int[R][26], next = new int[R][26];
Map<Character, List<Integer>> map = new HashMap<>();
for (int i = 0; i < ring.length(); i++) {
char ch = ring.charAt(i);
map.putIfAbsent(ch, new ArrayList<>());
map.get(ch).add(i);
}
for (char ch : map.keySet()) {
List<Integer> list = map.get(ch);
for (int i = 0, ptr = 0; i < ring.length(); i++) {
next[i][ch - 'a'] = list.get(ptr);
prev[i][ch - 'a'] = list.get((ptr - 1 + list.size()) % list.size());
if (ring.charAt(i) == ch) ptr = (ptr + 1) % list.size();
}
}
From O(m * n^2) to O(mn).
First, we preprocess the latest index for each letter going only in one direction. For example when we preprocess "abab" clockwise, we will have the following in the returned result:
0 3
0 1
2 1
2 3
After going through the ring twice, the answer will stablize.
0 3
0 1
2 1
2 3
After going through the ring twice, the answer will stablize.
Then we do DP:
state:
12:00 points to jth letter in ring, how many rotation steps required to spell letters starting from ith character
initialization:
dp[m+1][0~n] = 0 since zero steps required to spell empty string regardless of starting position
function:
Previous result + Min(going clockwise, going anticlockwise);
clockwise : this rotation start at j, end at p
anticlockwise : this rotation start at j, end at q
dp[i][j] = Math.min(dp[i + 1][p] + (j + n - p) % n, dp[i + 1][q] + (q + n - j) % n);
result:
dp[0][0] which is the original pattern, plus m steps to spell the word
state:
12:00 points to jth letter in ring, how many rotation steps required to spell letters starting from ith character
initialization:
dp[m+1][0~n] = 0 since zero steps required to spell empty string regardless of starting position
function:
Previous result + Min(going clockwise, going anticlockwise);
clockwise : this rotation start at j, end at p
anticlockwise : this rotation start at j, end at q
dp[i][j] = Math.min(dp[i + 1][p] + (j + n - p) % n, dp[i + 1][q] + (q + n - j) % n);
result:
dp[0][0] which is the original pattern, plus m steps to spell the word
public int findRotateSteps(String ring, String key) {
int n = ring.length(), m = key.length();
int[][] dp = new int[m + 1][n];
int[][] clock = preproc(ring, 1), anti = preproc(ring, -1);
for (int i = m - 1; i >= 0; --i) {
int idx = key.charAt(i) - 'a';
for (int j = 0; j < n; ++j) { // fill dp[i][j]
int p = clock[j][idx];
int q = anti[j][idx];
dp[i][j] = Math.min(dp[i + 1][p] + (j + n - p) % n, dp[i + 1][q] + (q + n - j) % n);
}
}
return dp[0][0] + m;
}
int[][] preproc(String r, int inc) {
int n = r.length();
int[][] ans = new int[n][26];
int[] map = new int[26];
for (int i = 0, j = 0; j < n * 2 - 1; ++j) {
map[r.charAt(i) - 'a'] = i;
System.arraycopy(map, 0, ans[i], 0, 26);
i = (i + inc + n) % n;
}
return ans;
}
public int findRotateSteps(String ring, String key) {
int R = ring.length(), K = key.length();
int[][] prev = new int[R][26], next = new int[R][26];
Map<Character, List<Integer>> map = new HashMap<>();
for (int i = 0; i < ring.length(); i++) {
char ch = ring.charAt(i);
map.putIfAbsent(ch, new ArrayList<>());
map.get(ch).add(i);
}
for (char ch : map.keySet()) {
List<Integer> list = map.get(ch);
for (int i = 0, ptr = 0; i < ring.length(); i++) {
next[i][ch - 'a'] = list.get(ptr);
prev[i][ch - 'a'] = list.get((ptr - 1 + list.size()) % list.size());
if (ring.charAt(i) == ch)
ptr = (ptr + 1) % list.size();
}
}
int[][] f = new int[K][R];
int ans = Integer.MAX_VALUE;
for (int i = 0; i < K; i++) {
for (int j = 0; j < R; j++) {
f[i][j] = Integer.MAX_VALUE / 2;
if (key.charAt(i) == ring.charAt(j)) {
if (i == 0)
f[i][j] = Math.min(f[i][j], dist(0, j, ring.length()));
else {
int preKey = key.charAt(i - 1) - 'a';
f[i][j] = Math.min(f[i][j], f[i - 1][prev[j][preKey]] + dist(prev[j][preKey], j, ring.length()));
f[i][j] = Math.min(f[i][j], f[i - 1][next[j][preKey]] + dist(next[j][preKey], j, ring.length()));
}
}
if (i == key.length() - 1)
ans = Math.min(ans, f[i][j]);
}
}
return ans + key.length();
}
private int dist(int i, int j, int n) {
return Math.min(Math.abs(i - j), n - Math.abs(i - j));
}
* O(n^3) DP
* f[i][j]: min total distance when correctly typed the first i letters in key and stopped at j-th position of the ring.
* <p>
* 1) Many states are illegal, but that is okay.
* 2) We can in fact compute f[i][j] in O(1) time, see the improved version.
public int findRotateSteps(String ring, String key) {
if (key.length() == 0) return 0;
int ans = Integer.MAX_VALUE;
int[][] f = new int[key.length() + 1][ring.length()];
Arrays.fill(f[0], Integer.MAX_VALUE / 2);
f[0][0] = 0;
for (int i = 1; i < f.length; i++) { // Index-i is shifted by 1.
for (int j = 0; j < ring.length(); j++) {
f[i][j] = Integer.MAX_VALUE / 2;
if (ring.charAt(j) == key.charAt(i - 1)) {
for (int k = 0; k < ring.length(); k++) {
f[i][j] = Math.min(f[i][j], f[i - 1][k] + Math.min(Math.abs(j - k), ring.length() - Math.abs(j - k)));
}
}
if (i == key.length()) ans = Math.min(ans, f[i][j]);
}
}
return ans + key.length();
}
- linear space dp
int findRotateSteps(string ring, string key) {
vector<int> pos[26];
int r = ring.size(), k = key.size();
for(int i=0;i<r;i++) pos[ring[i]-'a'].push_back(i);
vector<int> pre(r), cur(r,INT_MAX), *p_pre = &pre, *p_cur = &cur;
for(int i=k-1;i>=0;i--) {
for(int j=0;j<r;j++)
for(int nxt:pos[key[i]-'a']) {
int dist = abs(j-nxt);
(*p_cur)[j]=min((*p_cur)[j],min(dist,r-dist)+(*p_pre)[nxt]);
}
swap(p_pre,p_cur);
p_cur->assign(r,INT_MAX);
}
return (*p_pre)[0]+k;
}X. DFS + cache
- the fastest submission
public int findRotateSteps(String ring, String key) { if (ring == null) return 0; List<Integer>[] r = new List[26]; for (int i = 0; i < 26; i++) { r[i] = new ArrayList<Integer>(); } for (int i = 0; i < ring.length(); i++) { r[ring.charAt(i) - 'a'].add(i); } int[][] cache = new int[ring.length()][key.length()]; return search(r, ring.length(), 0, key, 0, cache); } private int search(List<Integer>[] ring, int len, int p, String key, int index, int[][] cache) { if (index == key.length()) return 0; if (cache[p][index] > 0) return cache[p][index]; char c = key.charAt(index); List<Integer> indices = ring[c - 'a']; int min = Integer.MAX_VALUE; for (int i: indices) { int oneDir = Math.abs(p - i); int otherDir = len - oneDir; min = Math.min(min, 1 + Math.min(oneDir, otherDir) + search(ring, len, i, key, index + 1, cache)); } cache[p][index] = min; return min; }
The dp is a 2D integer array, with height = the length of ring, with width = the length of key. So DP[i][j] represents that if we want to spell the next character key[j], and at the same time the 12:00 aligns with the ring[i], then what is the minimum steps to spell the whole key start at key[j]. If we finish the DP array, then the answer is just DP[0][0], which means the minimum steps to spell the whole key start at key[0], if currently 12:00 aligns with the ring[0], and this is exactly the original problem. And don't forget to plus the length of key, which is the steps we need to push the button.
// by fallcreek
public int findRotateSteps(String ring, String key) {
int[][] dp = new int[ring.length()][key.length()];
for(int[] line : dp) Arrays.fill(line, -1);
return helper(ring, 0, key, 0, dp) + key.length();
}
public int helper(String ring, int rIndex, String key, int kIndex, int[][] dp){
if(kIndex == key.length()) return 0;
if(dp[rIndex][kIndex] != -1) return dp[rIndex][kIndex];
char dest = key.charAt(kIndex);
int nextIndex = ring.indexOf(dest);
int sol = Integer.MAX_VALUE;
do{
int move = Math.min(Math.abs(rIndex - nextIndex), ring.length() - Math.abs(rIndex - nextIndex));
int remain = helper(ring, nextIndex, key, kIndex + 1, dp);
sol = Math.min(sol, move + remain);
nextIndex = ring.indexOf(dest, nextIndex + 1);
}while(nextIndex != -1);
dp[rIndex][kIndex] = sol;
return sol;
}
Hi There! The key point in the problem is to make decision whether to move clockwise or anticlockwise. Actually to get optimal answer, we have to move clockwise for some characters of
key and anti-clockwise for others. If apply brute force, then for each position in key we have two options,- Search for the character clockwise
- Search for the character anti-clockwise
To find optimal answer we need to try both options and get minimum of them. Thus, we obtain
dfs solution for the problem. But, there are duplicate calculation for some positions. Therefore, we need to memorize states. The state is defined by position of thering and the index of character in the key. This way, we can avoid calculating number of steps for the same state. Code will clarify the idea more. Map<String, Map<Integer, Integer>> memo;
public int findRotateSteps(String ring, String key) {
memo = new HashMap<>();
return dfs(ring, key, 0);
}
private int findPos(String ring, char ch){ // find first occurrence clockwise
return ring.indexOf(ch);
}
private int findBackPos(String ring, char ch){ //find first occurrence anti-clockwise
if(ring.charAt(0) == ch) return 0;
for(int i = ring.length()-1;i>0;i--){
if(ring.charAt(i) == ch) return i;
}
return 0;
}
private int dfs(String ring, String key, int i){
if(i == key.length()) return 0;
int res = 0;
char ch = key.charAt(i);
if(memo.containsKey(ring) && memo.get(ring).containsKey(i)) return memo.get(ring).get(i);
int f = findPos(ring, ch);
int b = findBackPos(ring, ch);
int forward = 1+f+dfs(ring.substring(f)+ring.substring(0, f), key, i+1);
int back = 1+ring.length()-b + dfs(ring.substring(b)+ring.substring(0, b),key, i+1);
res = Math.min(forward, back);
Map<Integer, Integer> ans = memo.getOrDefault(ring, new HashMap<>());
ans.put(i, res);
memo.put(ring, ans);
return res;
}
下面这种解法是用DFS来解的，我们需要做优化，也就是用memo数组来保存已经计算过的结果，否则大量的重复运算是无法通过OJ的。其实这里的memo数组也起到了跟上面解法中的dp数组相类似的作用，还有就是要注意数组v的作用，记录了每个字母在ring中的出现位置，由于ring中可能有重复字符，而且麻烦的情况是当前位置向两个方向分别转动相同的步数会分别到达两个相同的字符，这也是贪婪算法会失效的一个重要原因，而且也是上面的解法在找到ring[k] == key[i]并处理完之后不break的原因，因为后面还有可能找到。上面的迭代解法中使用到的变量i和j可以直接访问到，而在递归的写法中必须要把位置变量x和y当作参数导入进去，这样才能更新正确的地方
int findRotateSteps(string ring, string key) { int n = ring.size(), m = key.size(); vector<vector<int>> v(26); vector<vector<int>> memo(n, vector<int>(m)); for (int i = 0; i < n; ++i) v[ring[i] - 'a'].push_back(i); return helper(ring, key, 0, 0, v, memo); } int helper(string ring, string key, int x, int y, vector<vector<int>>&v, vector<vector<int>>& memo) { if (y == key.size()) return 0; if (memo[x][y]) return memo[x][y]; int res = INT_MAX, n = ring.size(); for (int k : v[key[y] - 'a']) { int diff = abs(x - k); int step = min(diff, n - diff); res = min(res, step + helper(ring, key, k, y + 1, v, memo)); } return memo[x][y] = res + 1; }https://blog.csdn.net/huanghanqian/article/details/77619766
可以发现，打完 y，再打 n 时，发现顺时针和逆时针都可以到n。选哪个呢？这时候需要根据之后的字母离得跟哪个n比较近来抉择。
因此 当前的选择 需要根据之后的情况来选择 min step 的情况，要用递归来做。使用纯递归会TLE，因此使用递归with memory。
主要的问题是决定 是顺时针转还是逆时针转。在 brute force , 对于每个需要打出来的字符有两种选择：
顺时针来搜索这个字符
逆时针来搜索这个字符
为了得到最优解，我们需要都尝试这两种情况，并且选择这两种情况中的 min steps。对于一些位置可能会有重复计算的情况，因此我们需要存储 states 。state 由两者定义：ring 中被作为12点的位置， key 中字符的索引。使用map来存储state ，避免相同的 state 被重复计算。map的key是 ring中12点位置的索引，value是<key中的索引 , 从key中的索引开始打出字符串需要的最少步骤>。
在代码的方法参数中，index是当前所需要打的字符的index，position_12是当前位于12点位置的字母在cs[]中的索引。
public int findRotateSteps(String ring, String key) {
char[] cs = ring.toCharArray();
HashMap<Integer, HashMap<Integer, Integer>> map = new HashMap<Integer, HashMap<Integer, Integer>>();
return findRotateSteps(cs, key, 0, 0, map);
}
public int findRotateSteps(char[] cs, String key, int index, int position_12,
HashMap<Integer, HashMap<Integer, Integer>> map) {
if (index == key.length()) {
return 0;
}
if (map.get(position_12) != null && map.get(position_12).get(index) != null) {
return map.get(position_12).get(index);
}
int n = cs.length;
int clockwisePointer = position_12;
int anticlockwisePointer = position_12;
char target = key.charAt(index);
int clockwiseStep = 0;
while (cs[clockwisePointer] != target) {
clockwisePointer = (clockwisePointer + 1) % n;
clockwiseStep++;
}
int anticlockwiseStep = 0;
while (cs[anticlockwisePointer] != target) {
anticlockwisePointer = (anticlockwisePointer - 1 + n) % n;// 因为-1%3=-1
anticlockwiseStep++;
}
int count = Math.min(clockwiseStep + 1 + findRotateSteps(cs, key, index + 1, clockwisePointer, map),
anticlockwiseStep + 1 + findRotateSteps(cs, key, index + 1, anticlockwisePointer, map));
HashMap<Integer, Integer> value = map.getOrDefault(position_12, new HashMap<Integer, Integer>());
value.put(index, count);
map.put(position_12, value);
return count;
}
http://blog.jerkybible.com/2017/03/18/LeetCode-514-Freedom-Trail/
dfs的解法比较好理解，找到和ring[i]相同的字母时，分别进行顺时针和逆时针的旋转，记录步数，然后在旋转完之后继续拼写下一个字母。这种解法要注意的是，在求解的过程中相同的状态会出现很多次，因此需要记录这些状态，避免重复计算。
Map<String, Map<Integer, Integer>> cache = new HashMap<>();public int findRotateSteps(String ring, String key) {if (ring == null || ring.length() <= 0 || key == null|| key.length() <= 0) {return 0;}return findRotateSteps(ring, key, 0);}public int findRotateSteps(String ring, String key, int index) {if (index == key.length()) {return 0;}String curRing = ring;char c = key.charAt(index);if (cache.containsKey(ring) && cache.get(ring).containsKey(index)) {return cache.get(ring).get(index);}int first = curRing.indexOf(c);int last = curRing.lastIndexOf(c);int firstStep = 1 + first+ findRotateSteps(rollString(curRing, first), key, index + 1);int lastStep = 1 + ring.length() - last+ findRotateSteps(rollString(curRing, last), key, index + 1);int step = Math.min(firstStep, lastStep);Map<Integer, Integer> indexStep = cache.getOrDefault(ring,new HashMap<Integer, Integer>());indexStep.put(index, step);cache.put(ring, indexStep);return step;}private String revertString(String str) {char[] strArray = str.toCharArray();int len = strArray.length;char temp;for (int i = 0; i < len / 2; i++) {temp = strArray[i];strArray[i] = strArray[len - i - 1];strArray[len - i - 1] = temp;}return String.valueOf(strArray);}private String rollString(String str, int index) {String first = revertString(str.substring(0, index));String second = revertString(str.substring(index));return revertString(first + second);}
- O(kr^2) Memoization. There are overlapping sub-problems in #1. We only need to process a substring of key once.
int findRotateSteps(string ring, string key) {
vector<int> pos[26];
int r = ring.size();
for(int i=0;i<r;i++) pos[ring[i]-'a'].push_back(i);
vector<vector<int>> mem(r,vector<int>(key.size()));
return findSteps(0, 0, ring, key, pos,mem);
}
int findSteps(int p1, int p2, string &ring, string &key, vector<int> pos[26],vector<vector<int>>& mem) {
if(p2==key.size()) return 0;
if(mem[p1][p2]) return mem[p1][p2];
int r = ring.size(), ms=INT_MAX;
for(int nxt:pos[key[p2]-'a']) {
int dist = abs(p1-nxt);
ms = min(ms,min(dist, r-dist)+findSteps(nxt,p2+1,ring,key,pos,mem));
}
return mem[p1][p2]=ms+1;
}题目来自于辐射4这个游戏。有一个圆盘，圆盘上有几个英文字母，圆盘12点方向代表当前选中的字母，通过这个圆盘拼出一个和题目一样的字符串，求出最小的步数。
圆盘可以顺时针或者逆时针旋转，每旋转一个字母代表1步，当12点方向是需要的英文字母时，按确定按钮，这个按也算一步。
有两种解法，一种是dfs，一种是动态规划。
dfs的解法比较好理解，找到和ring[i]相同的字母时，分别进行顺时针和逆时针的旋转，记录步数，然后在旋转完之后继续拼写下一个字母。这种解法要注意的是，在求解的过程中相同的状态会出现很多次，因此需要记录这些状态，避免重复计算。
https://discuss.leetcode.com/topic/81699/java-clear-solution-dfs-memoizationMap<String, Map<Integer, Integer>> cache = new HashMap<>();public int findRotateSteps(String ring, String key) {if (ring == null || ring.length() <= 0 || key == null|| key.length() <= 0) {return 0;}return findRotateSteps(ring, key, 0);}public int findRotateSteps(String ring, String key, int index) {if (index == key.length()) {return 0;}String curRing = ring;char c = key.charAt(index);if (cache.containsKey(ring) && cache.get(ring).containsKey(index)) {return cache.get(ring).get(index);}int first = curRing.indexOf(c);int last = curRing.lastIndexOf(c);int firstStep = 1 + first+ findRotateSteps(rollString(curRing, first), key, index + 1);int lastStep = 1 + ring.length() - last+ findRotateSteps(rollString(curRing, last), key, index + 1);int step = Math.min(firstStep, lastStep);Map<Integer, Integer> indexStep = cache.getOrDefault(ring,new HashMap<Integer, Integer>());indexStep.put(index, step);cache.put(ring, indexStep);return step;}private String revertString(String str) {char[] strArray = str.toCharArray();int len = strArray.length;char temp;for (int i = 0; i < len / 2; i++) {temp = strArray[i];strArray[i] = strArray[len - i - 1];strArray[len - i - 1] = temp;}return String.valueOf(strArray);}private String rollString(String str, int index) {String first = revertString(str.substring(0, index));String second = revertString(str.substring(index));return revertString(first + second);}
The key point in the problem is to make decision whether to move clockwise or anticlockwise. Actually to get optimal answer, we have to move clockwise for some characters of
key and anti-clockwise for others. If apply brute force, then for each position in key we have two options,- Search for the character clockwise
- Search for the character anti-clockwise
To find optimal answer we need to try both options and get minimum of them. Thus, we obtain
dfs solution for the problem. But, there are duplicate calculation for some positions. Therefore, we need to memorize states. The state is defined by position of thering and the index of character in the key. This way, we can avoid calculating number of steps for the same state. Code will clarify the idea more. Map<String, Map<Integer, Integer>> memo;
public int findRotateSteps(String ring, String key) {
memo = new HashMap<>();
return dfs(ring, key, 0);
}
private int findPos(String ring, char ch){ // find first occurrence clockwise
return ring.indexOf(ch);
}
private int findBackPos(String ring, char ch){ //find first occurrence anti-clockwise
if(ring.charAt(0) == ch) return 0;
for(int i = ring.length()-1;i>0;i--){
if(ring.charAt(i) == ch) return i;
}
return 0;
}
private int dfs(String ring, String key, int i){
if(i == key.length()) return 0;
int res = 0;
char ch = key.charAt(i);
if(memo.containsKey(ring) && memo.get(ring).containsKey(i)) return memo.get(ring).get(i);
int f = findPos(ring, ch);
int b = findBackPos(ring, ch);
int forward = 1+f+dfs(ring.substring(f)+ring.substring(0, f), key, i+1);
int back = 1+ring.length()-b + dfs(ring.substring(b)+ring.substring(0, b),key, i+1);
res = Math.min(forward, back);
Map<Integer, Integer> ans = memo.getOrDefault(ring, new HashMap<>());
ans.put(i, res);
memo.put(ring, ans);
return res;
}X. brute force, try all next steps.
https://discuss.leetcode.com/topic/82720/evolve-from-brute-force-to-dp
int findRotateSteps(string ring, string key) {
vector<int> pos[26];
for(int i=0;i<ring.size();i++) pos[ring[i]-'a'].push_back(i);
return findSteps(0, 0, ring, key, pos);
}
int findSteps(int p1, int p2, string &ring, string &key, vector<int> pos[26]) {
if(p2==key.size()) return 0;
int r = ring.size(), ms=INT_MAX;
for(int nxt:pos[key[p2]-'a']) {
int dist = abs(p1-nxt);
ms = min(ms,min(dist, r-dist)+findSteps(nxt,p2+1,ring,key,pos));
}
return ms+1;
}