Problem statement

https://leetcode.com/problems/freedom-trail/

Solution

Let us denote by dp(i, j) the smallest number of steps, when we on the place j and we already used i symbols from key. How we can reach this place? We need to check two closest places: one to the left and one to the right from where we can reach this place. For this we need to preprocess our data, using function letter_get(s, letter, dr), where s is string, letter is symbol we are looking for and dr is direction, which is either 1 or -1. We evaluate dir_pl and dir_mn, which have precalculated places for next positions for each letter for clockwise and counterclockwise directions. Complexity of this step is O(26n)`.

So, now we can have access to closest left and right symbols in O(1), so we can fill our dynamic programming table, each time choosing one of the two best options.

Complexity

We can estimate time complexity as O(mn), because we visit each cell only once. However, complexity is even better. Let $q_1,\dots, q_{26}$ be frequencies of letters in ring array. Then we visit at most $q_{k_1} + \dots + q_{k_m}$ states, where $k_1, \dots k_m$ are letters from key. Overall complexity for dfs can be estimated as $O(m\cdot \max\limits_{i} q_i)$. Note, that if we use usual dp, than we do $\Omega(mn)$ operations at least, so it will work much slower, because of sparse structure of problem. Finally, time complexity is $O(m\cdot \max\limits_{i} q_i + 26n)$ and space complexity is $O(26n)$.

Code

class Solution:
    def findRotateSteps(self, ring, key):
        def letter_get(s, letter, dr):
            start = s.index(letter)
            n = len(s) 
            res = [0]*n
            for j in range(start, start-n*dr, -dr):
                if s[j%n] == letter: start = j
                res[j%n] = start%n
            return res
        
        n, m = len(ring), len(key)
        dir_pl, dir_mn = defaultdict(list), defaultdict(list)
        
        for letter in set(ring):
            dir_mn[letter] = letter_get(ring, letter, 1)
            dir_pl[letter] = letter_get(ring, letter, -1)
        
        @lru_cache(None)
        def dp(i, j):
            if i == 0: return min(j, n-j)
            p, q = dir_pl[key[i-1]][j], dir_mn[key[i-1]][j]    
            return min(dp(i-1, p) + (j-p)%n, dp(i-1, q) + (q-j)%n)
        
        return min([dp(m-1, i) for i in range(n) if key[-1] == ring[i]]) + m