2024.1.29力扣每日一题——自由之路

2024.1.29

• • • 题目来源
    • 我的题解
    • • 方法一 动态规划

题目来源

力扣每日一题；题序：514

我的题解

方法一 动态规划

定义 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]，表示字符 ii在 ring 中出现的位置集合，用来加速计算转移的过程。

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

dp

[

i

]

[

j

]

=

min

⁡

k

∈

p

o

s

[

k

e

y

[

i

−

1

]

]

{

d

p

[

i

−

1

]

[

k

]

+

min

⁡

{

abs

(

j

−

k

)

,

n

−

abs

(

j

−

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

dp[i][j]=mink∈pos[key[i−1]]​{dp[i−1][k]+min{abs(j−k),n−abs(j−k)}}

其中

min

⁡

{

abs

(

j

−

k

)

,

n

−

abs

(

j

−

k

)

}

\min\{\text{abs}(j-k),n-\text{abs}(j-k)\}

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

最后答案即为

min

⁡

i

=

0

n

−

1

{

dp

[

m

−

1

]

[

i

]

}

+

m

\min_{i=0}^{n-1}\{\textit{dp}[m-1][i]\}+m

mini=0n−1​{dp[m−1][i]}+m。

时间复杂度： O(

m

n

2

mn^2

mn2)

空间复杂度： O(mn)

public int findRotateSteps(String ring, String key) {
    int n = ring.length(), m = key.length();
    //存储每个字符所在的位置
    List[] 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);
    }
    int[][] dp = new int[m][n];
    for (int i = 0; i < m; ++i) {
        Arrays.fill(dp[i], Integer.MAX_VALUE);
    }
    for (int i : pos[key.charAt(0) - 'a']) {
        dp[0][i] = Math.min(i, n - i);
    }
    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)));
            }
        }
    }

    return Arrays.stream(dp[m - 1]).min().getAsInt()+m;
    }

//优化空间版本
// 考虑到每次转移状态 dp[i][] 只会从 dp[i−1][] 转移过来，因此可以利用滚动数组优化第一维的空间复杂度

    public int findRotateSteps(String ring, String key) {
        int n = ring.length(), m = key.length();
        List[] 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);
        }
        //空间优化，dp[]
        int[] dp = new int[n];
        for (int i : pos[key.charAt(0) - 'a']) 
            dp[i] = Math.min(i, n - i);
        for (int i = 1; i < m; ++i) {
            //若当前与上一次相同则不需要转动ring
            if(key.charAt(i)==key.charAt(i-1))
                continue;
            for (int j : pos[key.charAt(i) - 'a']) {
                dp[j]=Integer.MAX_VALUE;
                for (int k : pos[key.charAt(i - 1) - 'a']) {
                    dp[j] = Math.min(dp[j], dp[k] + Math.min(Math.abs(j - k), n - Math.abs(j - k)));
                }
            }
        }
        return pos[key.charAt(m - 1) - 'a'].stream()
                .mapToInt(i -> dp[i])
                .min()
                .orElse(Integer.MAX_VALUE)+m;
    }

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~