0514-自由之路

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:32 2023-09-13 16:06:32 Updated    

电子游戏“辐射4”中，任务 “通向自由” 要求玩家到达名为 “ Freedom Trail Ring”
的金属表盘，并使用表盘拼写特定关键词才能开门。

给定一个字符串 ring ，表示刻在外环上的编码；给定另一个字符串 key ，表示需要拼写的关键词。您需要算出能够拼写关键词中所有字符的
最少 步数。

最初， **ring **的第一个字符与 12:00 方向对齐。您需要顺时针或逆时针旋转 ring 以使 **key **的一个字符在
12:00 方向对齐，然后按下中心按钮，以此逐个拼写完 **key **中的所有字符。

旋转 ring ** ** 拼出 key 字符 key[i] ** ** 的阶段中：

  1. 您可以将 **ring **顺时针或逆时针旋转 **一个位置 **，计为1步。旋转的最终目的是将字符串 **ring **的一个字符与 12:00 方向对齐，并且这个字符必须等于字符 key[i] 。
  2. 如果字符 **key[i] **已经对齐到12:00方向，您需要按下中心按钮进行拼写，这也将算作 1 步 。按完之后，您可以开始拼写 **key **的下一个字符（下一阶段）, 直至完成所有拼写。

示例 1：

**输入:** ring = "godding", key = "gd"
**输出:** 4
**解释:**
 对于 key 的第一个字符 'g'，已经在正确的位置, 我们只需要1步来拼写这个字符。 
 对于 key 的第二个字符 'd'，我们需要逆时针旋转 ring "godding" 2步使它变成 "ddinggo"。
 当然, 我们还需要1步进行拼写。
 因此最终的输出是 4。

示例 2:

**输入:** ring = "godding", key = "godding"
**输出:** 13

提示：

  • 1 <= ring.length, key.length <= 100
  • ring 和 key 只包含小写英文字母
  • 保证 字符串 key 一定可以由字符串 ring 旋转拼出

方法一：动态规划

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

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

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

\textit{dp}[i][j]=\min_{k \in pos[key[i-1]]}{dp[i-1][k]+\min{\text{abs}(j-k),n-\text{abs}(j-k)}+1}

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

最后答案即为 \min_{i=0}^{n-1}{\textit{dp}[m-1][i]\。

这样的做法需要开辟 O(mn) 的空间来存放 dp 值。考虑到每次转移状态 dp}[i][] 只会从 dp}[i-1][] 转移过来，因此我们可以利用滚动数组优化第一维的空间复杂度，有能力的读者可以尝试实现。下面只给出最朴素的 O(mn) 空间复杂度的实现。

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int findRotateSteps(string ring, string key) {
        int n = ring.size(), m = key.size();
        vector<int> pos[26];
        for (int i = 0; i < n; ++i) {
            pos[ring[i] - 'a'].push_back(i);
        }
        vector<vector<int>> dp(m, vector<int>(n, 0x3f3f3f3f));
        for (auto& i: pos[key[0] - 'a']) {
            dp[0][i] = min(i, n - i) + 1;
        }
        for (int i = 1; i < m; ++i) {
            for (auto& j: pos[key[i] - 'a']) {
                for (auto& k: pos[key[i - 1] - 'a']) {
                    dp[i][j] = min(dp[i][j], dp[i - 1][k] + min(abs(j - k), n - abs(j - k)) + 1);
                }
            }
        }
        return *min_element(dp[m - 1].begin(), dp[m - 1].end());
    }
};
[sol1-Java]
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
class Solution {
    public int findRotateSteps(String ring, String key) {
        int n = ring.length(), m = key.length();
        List<Integer>[] pos = new List[26];
        for (int i = 0; i < 26; ++i) {
            pos[i] = new ArrayList<Integer>();
        }
        for (int i = 0; i < n; ++i) {
            pos[ring.charAt(i) - 'a'].add(i);
        }
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; ++i) {
            Arrays.fill(dp[i], 0x3f3f3f);
        }
        for (int i : pos[key.charAt(0) - 'a']) {
            dp[0][i] = Math.min(i, n - i) + 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();
    }
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const getIdx = (str, v) => str.codePointAt(v) - 'a'.codePointAt(0);
var findRotateSteps = function(ring, key) {
    const n = ring.length, m = key.length;
    const pos = new Array(26).fill(0).map(v => []);
    for (let i = 0; i < n; ++i) {
        pos[getIdx(ring, i)].push(i);
    }
    const dp = new Array(m).fill(0).map(v => new Array(n).fill(Number.MAX_SAFE_INTEGER));
    for (const i of pos[getIdx(key, 0)]) {
        dp[0][i] = Math.min(i, n - i) + 1;
    }
    for (let i = 1; i < m; ++i) {
        for (const j of pos[getIdx(key, i)]) {
            for (const k of pos[getIdx(key, i - 1)]) {
                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 dp[m - 1].reduce((pre, cur) => Math.min(pre, cur), Number.MAX_SAFE_INTEGER);
};
[sol1-Golang]
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
32
33
34
35
36
37
38
39
40
41
42
43
func findRotateSteps(ring string, key string) int {
    const inf = math.MaxInt64 / 2
    n, m := len(ring), len(key)
    pos := [26][]int{}
    for i, c := range ring {
        pos[c-'a'] = append(pos[c-'a'], i)
    }
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
        for j := range dp[i] {
            dp[i][j] = inf
        }
    }
    for _, p := range pos[key[0]-'a'] {
        dp[0][p] = min(p, n-p) + 1
    }
    for i := 1; i < m; i++ {
        for _, j := range pos[key[i]-'a'] {
            for _, k := range pos[key[i-1]-'a'] {
                dp[i][j] = min(dp[i][j], dp[i-1][k]+min(abs(j-k), n-abs(j-k))+1)
            }
        }
    }
    return min(dp[m-1]...)
}

func min(a ...int) int {
    res := a[0]
    for _, v := range a[1:] {
        if v < res {
            res = v
        }
    }
    return res
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}
[sol1-C]
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
int findRotateSteps(char* ring, char* key) {
    int n = strlen(ring), m = strlen(key);
    int pos[26][n], posSize[26];
    memset(posSize, 0, sizeof(posSize));
    for (int i = 0; i < n; ++i) {
        int x = ring[i] - 'a';
        pos[x][posSize[x]++] = i;
    }
    int dp[m][n];
    memset(dp, 0x3f3f3f3f, sizeof(dp));
    for (int i = 0; i < posSize[key[0] - 'a']; i++) {
        int x = pos[key[0] - 'a'][i];
        dp[0][x] = fmin(x, n - x) + 1;
    }
    for (int i = 1; i < m; ++i) {
        for (int j = 0; j < posSize[key[i] - 'a']; ++j) {
            int x = pos[key[i] - 'a'][j];
            for (int k = 0; k < posSize[key[i - 1] - 'a']; ++k) {
                int y = pos[key[i - 1] - 'a'][k];
                dp[i][x] = fmin(dp[i][x], dp[i - 1][y] + fmin(abs(x - y), n - abs(x - y)) + 1);
            }
        }
    }
    int ret = dp[m - 1][0];
    for (int i = 1; i < n; ++i) {
        ret = fmin(ret, dp[m - 1][i]);
    }
    return ret;
}

复杂度分析

  • 时间复杂度：O(mn^2)，其中 m 为字符串 key 的长度，n 为字符串 ring 的长度。一共有 O(mn) 个状态要计算，每次转移的时间复杂度为 O(n)，因此时间复杂度为 O(mn^2)。
    由于维护了位置数组 pos 加速了状态的计算与转移，因此 O(mn^2) 是一个较松的上界，很多情况下的时间复杂度都会低于 O(mn^2)。

  • 空间复杂度：O(mn)。需要使用 O(mn) 的空间来存放 dp 数组，以及使用 O(n) 的空间来存放 pos 数组，因此总空间复杂度为 O(mn)。如果利用滚动数组，则可以将 dp 数组的空间复杂度降低到 O(n)，总空间复杂度降低到 O(n)。

 Comments
On this page
0514-自由之路