Sponsored
Sponsored
In this approach, we'll use a recursive solution with memoization to efficiently calculate the minimum number of steps. The function will take the current position in the ring and the current index in the key string as parameters, and will calculate the optimal steps required for each character. We'll cache the results of subproblems to avoid recalculating them.
Time Complexity: O(m*n), where m is the length of the `key` and n is the length of the `ring`.
Space Complexity: O(m*n) for the memoization table and index dictionary.
1import java.util.*;
2
3public class FreedomTrail {
4 public int minSteps(String ring, String key) {
5 Map<Character, List<Integer>> ringIndices = new HashMap<>();
6 for (int i = 0; i < ring.length(); i++) {
7 ringIndices.computeIfAbsent(ring.charAt(i), k -> new ArrayList<>()).add(i);
8 }
9 int[][] memo = new int[ring.length()][key.length()];
10 return dp(ring, key, 0, 0, ringIndices, memo);
11 }
12
13 private int dp(String ring, String key, int pos, int idx, Map<Character, List<Integer>> ringIndices, int[][] memo) {
14 if (idx == key.length()) return 0;
15 if (memo[pos][idx] != 0) return memo[pos][idx];
16
17 int res = Integer.MAX_VALUE;
18 for (int k : ringIndices.get(key.charAt(idx))) {
19 int diff = Math.abs(pos - k);
20 int step = Math.min(diff, ring.length() - diff) + 1;
21 res = Math.min(res, step + dp(ring, key, k, idx + 1, ringIndices, memo));
22 }
23 memo[pos][idx] = res;
24 return res;
25 }
26
27 public static void main(String[] args) {
28 FreedomTrail ft = new FreedomTrail();
29 System.out.println(ft.minSteps("godding", "gd")); // Output: 4
30 }
31}This Java solution is a translation of the Python approach using dynamic programming and memoization. We store indices of characters in the ring using a Map, and then use a recursive helper function `dp` to calculate the optimal steps. The `memo` array is used to cache results for specific states of `pos` and `idx` to reduce redundant calculations.
In this approach, we'll leverage BFS to explore each possible state of the ring and propagate the minimum distance for each configuration. We can view each state as a node in a graph and use BFS to find the target node with minimum steps.
Time Complexity: O(n*m), where n is the length of the key and m is the length of the ring.
Space Complexity: O(n*m) for storing visited states in the queue.
1from collections import deque, defaultdict
2
3
This solution uses a breadth-first search (BFS) approach to explore each state (current position and current character index in the key string). Each state is added to a queue along with the action step count. For each character in the key, we consider all possible indices in the ring where the character appears and add them to the queue, marking them as visited.