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$)
空间复杂度： O(mn)

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], 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<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);}//空间优化，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) {//若当前与上一次相同则不需要转动ringif(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;}

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