Problem statement

https://binarysearch.com/problems/Double-String-Concatenation/

Solution

This problem is about edit distance: split word into two parts and then find edit distance between two parts.

Complexity

It is O(n^3) for time and O(n^2) for space.

Code

class Solution:
    def solve(self, s):
        def dist(w1, w2):
            @lru_cache(None)
            def dp(i, j):
                if j == -1: return i + 1
                if i == -1: return j + 1
                cost = w1[i] != w2[j]
                return min(dp(i-1,j) + 1, dp(i,j-1) + 1, dp(i-1,j-1) + cost)
            
            return dp(len(w1) - 1, len(w2) - 1)

        if not s: return 0
        return min(dist(s[:i], s[i:]) for i in range(len(s)))