BinarySearch 0201 Longest Common Subsequence of Three Strings

Problem statement

https://binarysearch.com/problems/Longest-Common-Subsequence-of-Three-Strings/

Solution

We use state dp(i, j, k) is answer for a[:i+1], b[:j+1], c[:k+1].

Complexity

It is O(mnk) for time and space.

Code

class Solution:
    def solve(self, a, b, c):
        n, m, k = len(a), len(b), len(c)
        @lru_cache(None)
        def dp(i, j, k):
            if min(i, j, k) == -1: return 0
            if min(i, j, k) < -1: return float("inf")
            if a[i] == b[j] == c[k]:
                return 1 + dp(i - 1, j - 1, k - 1)
            else:
                return max(dp(i, j, k - 1), dp(i, j - 1, k), dp(i - 1, j, k))

        return dp(n - 1, m - 1, k - 1)