## Freedom Trail

• Time:O(kr^2), where k = |\texttt{key}| and r = |\texttt{ring}|
• Space:O(k)

## C++

``````class Solution {
public:
int findRotateSteps(string ring, string key) {
return dfs(ring, key, 0, {}) + key.length();
}

private:
// # of rotates of ring to match key[index:]
int dfs(const string& ring, const string& key, int index,
unordered_map<string, int>&& memo) {
if (index == key.length())
return 0;
// add the index to prevent duplicate
const string hashKey = ring + to_string(index);
if (memo.count(hashKey))
return memo[hashKey];

int ans = INT_MAX;

// for each ring[i] == key[index]
// we rotate the ring to match ring[i] w/ key[index]
// then recursively match newRing w/ key[index + 1:]
for (size_t i = 0; i < ring.length(); ++i)
if (ring[i] == key[index]) {
const int minRotates = min(i, ring.length() - i);
const string& newRing = ring.substr(i) + ring.substr(0, i);
const int remainingRotates = dfs(newRing, key, index + 1, move(memo));
ans = min(ans, minRotates + remainingRotates);
}

return memo[hashKey] = ans;
}
};
``````

## JAVA

``````class Solution {
public int findRotateSteps(String ring, String key) {
Map<String, Integer> memo = new HashMap<>();
return dfs(ring, key, 0, memo) + key.length();
}

// # of rotates of ring to match key[index:]
private int dfs(final String ring, final String key, int index, Map<String, Integer> memo) {
if (index == key.length())
return 0;
// add the index to prevent duplicate
final String hashKey = ring + index;
if (memo.containsKey(hashKey))
return memo.get(hashKey);

int ans = Integer.MAX_VALUE;

// for each ring[i] == key[index]
// we rotate the ring to match ring[i] w/ key[index]
// then recursively match newRing w/ key[index + 1:]
for (int i = 0; i < ring.length(); ++i)
if (ring.charAt(i) == key.charAt(index)) {
final int minRotates = Math.min(i, ring.length() - i);
final String newRing = ring.substring(i) + ring.substring(0, i);
final int remainingRotates = dfs(newRing, key, index + 1, memo);
ans = Math.min(ans, minRotates + remainingRotates);
}

memo.put(hashKey, ans);
return ans;
}
}
``````

## Python

``````class Solution:
def findRotateSteps(self, ring: str, key: str) -> int:
# number of rotates of ring to match key[index:]
@lru_cache(None)
def dfs(ring: str, index: int) -> int:
if index == len(key):
return 0

ans = math.inf

# for each ring[i] == key[index]
# we rotate the ring to match ring[i] w/ key[index]
# then recursively match newRing w/ key[index + 1:]
for i, r in enumerate(ring):
if r == key[index]:
minRotates = min(i, len(ring) - i)
newRing = ring[i:] + ring[:i]
remainingRotates = dfs(newRing, index + 1)
ans = min(ans, minRotates + remainingRotates)

return ans

return dfs(ring, 0) + len(key)
``````