K-Similar Strings LeetCode solution in Python

1
class Solution:
2
    def kSimilarity(self, s1: str, s2: str) -> int:
3
        n = len(s1)
4

5
        def helper(i, curr, dp):
6
            if curr == s2:
7
                return 0
8

9
            if curr not in dp[i]:
10
                if curr[i] == s2[i]:
11
                    dp[i][curr] = helper(i + 1, curr, dp)
12
                else:
13
                    temp = sys.maxsize
14
                    for j in range(i + 1, n):
15
                        if curr[j] == s2[i]:
16
                            temp = min(
17
                                temp,
18
                                1
19
                                + helper(
20
                                    i + 1,
21
                                    curr[:i]
22
                                    + curr[j]
23
                                    + curr[i + 1 : j]
24
                                    + curr[i]
25
                                    + curr[j + 1 :],
26
                                    dp,
27
                                ),
28
                            )
29

30
                    dp[i][curr] = temp
31
            return dp[i][curr]
32

33
        dp = [{} for _ in range(n)]
34
        return helper(0, s1, dp)