514.自由之路

链接：514.自由之路
难度：Hard
标签：深度优先搜索、广度优先搜索、字符串、动态规划
简介：给定一个字符串 ring ，表示刻在外环上的编码；给定另一个字符串 key ，表示需要拼写的关键词。您需要算出能够拼写关键词中所有字符的最少步数。

题解 1 - javascript

• 编辑时间：2020-11-11
• 执行用时：140ms
• 内存消耗：45.82MB
• 编程语言：javascript
• 解法介绍：dp。

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);
};

题解 2 - python

• 编辑时间：2024-01-29
• 执行用时：108ms
• 内存消耗：17.4MB
• 编程语言：python
• 解法介绍：dfs。

class Solution:
    def findRotateSteps(self, ring: str, key: str) -> int:
        arr = defaultdict(list)
        for i in range(len(ring)):
            arr[ring[i]].append(i)
        @cache
        def dfs(i1: int, i2: int) -> int:
            if i2 == len(key): return 0
            if ring[i1] == key[i2]: return dfs(i1, i2 + 1) + 1
            return min(
                dfs(next_i, i2 + 1) + min(abs(i1 - next_i), len(ring) - abs(i1 - next_i)) + 1
                for next_i in arr[key[i2]]
            )
        return dfs(0, 0)