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.
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4#include <algorithm>
5
6using namespace std;
7
8class FreedomTrail {
9public:
10 int findRotateSteps(string ring, string key) {
11 unordered_map<char, vector<int>> ringIndices;
12 for (int i = 0; i < ring.size(); ++i) {
13 ringIndices[ring[i]].push_back(i);
14 }
15 vector<vector<int>> memo(ring.size(), vector<int>(key.size(), -1));
16 return dp(ring, key, 0, 0, ringIndices, memo);
17 }
18
19private:
20 int dp(const string &ring, const string &key, int pos, int idx,
21 unordered_map<char, vector<int>> &ringIndices, vector<vector<int>> &memo) {
22 if (idx == key.size()) return 0;
23 if (memo[pos][idx] != -1) return memo[pos][idx];
24
25 int res = INT_MAX;
26 for (int k : ringIndices[key[idx]]) {
27 int diff = abs(pos - k);
28 int step = min(diff, (int)ring.size() - diff) + 1;
29 res = min(res, step + dp(ring, key, k, idx + 1, ringIndices, memo));
30 }
31 memo[pos][idx] = res;
32 return res;
33 }
34};
35
36int main() {
37 FreedomTrail ft;
38 cout << ft.findRotateSteps("godding", "gd") << endl; // Output: 4
39 return 0;
40}This C++ implementation adopts a dynamic programming approach with memoization to compute the minimum steps required. We use an unordered_map to store indices of each character in the ring for quick access. A recursive method `dp` calculates the minimum steps for each state while caching results in a `memo` table to prevent redundant computations.
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.