自由之路

发表于
本文字数： 2.9k 阅读时长 ≈ 3 分钟

LeetCode每日一题，514. Freedom Trail

先看题目描述

BXYi5j.png

大意就是给定两个字符串，一个字符串 ring 表示刻在外环上的编码，另一个字符串 key 表示需要拼接的关键词，让我们算出能够拼写关键词中所有字符的最少步数

算法思路

这题不会，我是直接看的题解…

动态规划

定义 dp[i][j] 表示从前往后拼写出 key 的第 i 个字符， ring 的第 j 个字符与12:00 方向对齐的最少步数（下标均从 0 开始）

显然，只有当字符串 ring 的第 j 个字符和 key 的第 i 个字符相同时才能拼写出 key 的第 i 个字符，因此对于 key 的第 i 个字符，需要考虑其在 ring 中出现的下标集合。我们对每个字符维护一个位置数组 pos[i]，表示字符 i 在 ring 中出现的位置集合，用来加速计算转移的过程

对于状态 dp[i][j]，需要枚举上一次与 12:00 方向对齐的位置 k，因此可以列出如下的转移方程：

BXNIK0.png

其中 min{abs(j - k), n - abs(j - k)} 表示在当前第 k 个字符与 12:00 方向对齐时第 j 个字符旋转到 12:00 方向并按下拼写的最少步数

最后返回数组 dp[m - 1] 中的最小值即可

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.*;

class Solution {
    public int findRotateSteps(String ring, String key) {
        int m = key.length();
        int n = ring.length();
        int[][] dp = new int[m][n];
        List<Integer>[] pos = new List[26];
        for (int i = 0; i < 26; i++) {
            pos[i] = new ArrayList<>();
        }
        for (int i = 0; i < n; i++) {
            pos[ring.charAt(i) - 'a'].add(i);
        }
        for (int i = 0; i < m; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        for (int index : pos[key.charAt(0) - 'a']) {
            dp[0][index] = Math.min(index, n - index) + 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j : pos[key.charAt(i) - 'a']) {
                for (int k : pos[key.charAt(i - 1) - 'a']) {
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + Math.min(Math.abs(j - k), n - Math.abs(j - k)) + 1);
                }
            }
        }
        return Arrays.stream(dp[m - 1]).min().getAsInt();
    }
}

利用滚动数组优化空间复杂度后的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.*;

class Solution {
    public int findRotateSteps(String ring, String key) {
        int m = key.length();
        int n = ring.length();
        int[][] dp = new int[2][n];
        List<Integer>[] pos = new List[26];
        // Arrays.fill(pos, new ArrayList<>());
        for (int i = 0; i < 26; i++) {
            pos[i] = new ArrayList<>();
        }
        for (int i = 0; i < n; i++) {
            pos[ring.charAt(i) - 'a'].add(i);
        }
        Arrays.fill(dp[0], Integer.MAX_VALUE);
        for (int index: pos[key.charAt(0) - 'a']) {
            dp[0][index] = Math.min(index, n - index) + 1;
        }
        for (int i = 1; i < m; i++) {
            int row = i % 2;
            Arrays.fill(dp[row], Integer.MAX_VALUE);
            for (int j : pos[key.charAt(i) - 'a']) {
                for (int k : pos[key.charAt(i - 1) - 'a']) {
                    dp[row][j] = Math.min(dp[row][j], dp[1 - row][k] + Math.min(Math.abs(j - k), n - Math.abs(j - k)) + 1);
                }
            }
        }
        return Arrays.stream(dp[(m - 1) % 2]).min().getAsInt();
    }
}

注意在对列表数组 pos 初始化时不能用 Arrays.fill()，否则 pos 中的所有元素实际上指向的是是同一个列表