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.
1import java.util.*;
2
This Java solution implements a BFS to traverse all possible configurations of the ring state. The queue holds the current position and index of the key. We exhaust each potential state for each character in the key by leveraging a set to track visited states for efficiency.