Участник:Easik/freedom-trail

Материал из DISCOPAL
Перейти к: навигация, поиск

Python 3

class Solution(object):
 
    def findRotateSteps(self, ring: str, key: str) -> int:
        """
        :type ring: str
        :type key: str
        :rtype: int
        """
 
        self.key = key
 
        min_ring_rotations = self.dfs(ring, 0)
        spelling_num = len(key)
 
        return min_ring_rotations + spelling_num
 
 
    # Depth First Search
    @lru_cache(None)
    def dfs(self, ring, idx):
        """
        :param ring: current ring configuration
        :param idx: current idx in a key
        :return: minimum rotations
        """
 
        # Possible combinations completed
        if idx == len(self.key):
            return 0
 
        ret = 100000000
 
        # Search for corresponding item in a ring
        for i in range(len(ring)):
 
            # Proceed only with valid sub-combinations
            if ring[i] == self.key[idx]:
 
                # Calc min rotations
                min_rotations = min(i, len(ring) - i)
                min_other_rotations = self.dfs(ring[i:] + ring[:i], idx + 1)
                ret = min(ret, min_rotations + min_other_rotations)
 
        return ret