-
Notifications
You must be signed in to change notification settings - Fork 0
/
FreedomTrail.java
35 lines (30 loc) · 1.26 KB
/
FreedomTrail.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/* https://leetcode.com/problems/freedom-trail/?envType=daily-question&envId=2024-04-27 */
/* 514. Freedom Trail */
class FreedomTrail {
public int findRotateSteps(String ring, String key) {
Map<String, Integer> mem = new HashMap<>();
return dfs(ring, key, 0, mem) + key.length();
}
// Returns the number of rotates of ring to match key[index..n).
private int dfs(final String ring, final String key, int index, Map<String, Integer> mem) {
if (index == key.length())
return 0;
// Add the index to prevent duplication.
final String hashKey = ring + index;
if (mem.containsKey(hashKey))
return mem.get(hashKey);
int ans = Integer.MAX_VALUE;
// For each ring[i] == key[index], we rotate the ring to match the ring[i]
// with the key[index], then recursively match the newRing with the
// key[index + 1..n).
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, mem);
ans = Math.min(ans, minRotates + remainingRotates);
}
mem.put(hashKey, ans);
return ans;
}
}