Skip to content

514. Freedom Trail 👍

  • Time: $O(kr^2)$, where $k = |\texttt{key}|$ and $r = |\texttt{ring}|$
  • Space: $O(k)$
 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
class Solution {
 public:
  int findRotateSteps(string ring, string key) {
    return dfs(ring, key, 0, {}) + key.length();
  }

 private:
  // Returns the number of rotates of ring to match key[index..n).
  int dfs(const string& ring, const string& key, int index,
          unordered_map<string, int>&& mem) {
    if (index == key.length())
      return 0;
    // Add the index to prevent duplication.
    const string hashKey = ring + to_string(index);
    if (const auto it = mem.find(hashKey); it != mem.cend())
      return it->second;

    int ans = INT_MAX;

    // 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 (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, std::move(mem));
        ans = min(ans, minRotates + remainingRotates);
      }

    return mem[hashKey] = ans;
  }
};

 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
class Solution {
  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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
  def findRotateSteps(self, ring: str, key: str) -> int:
    @functools.lru_cache(None)
    def dfs(ring: str, index: int) -> int:
      """Returns the number of rotates of ring to match key[index..n)."""
      if index == len(key):
        return 0

      ans = math.inf

      # 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 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)