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
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 (const auto it = memo.find(hashKey); it != memo.cend())
      return it->second;

    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;
  }
};

 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> 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;
  }
}

 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:
    # Number of rotates of ring to match key[index:]
    @functools.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)