Leetcode: 2060. Check if an Original String Exists Given Two Encoded Strings

Mistake: Missing edge case. Did not check for ab and aN where N is any number.
Mistake: Wrong time complexity. Thought that the problem was Backtracking and missed that I could memoize the params to speed up the solution.
How can we extend the solution for \(i\) to \(i+1\)? The search space is defined by \((i, w1, j, w2)\) where \(i\) and \(j\) are the next position to be processed on \(s1\) and \(s2\) respectively after \(w1\) and \(w2\) wild chars are processed. Space complexity is then \(O(n^2)\) with big constant of since \(w1 \times w2 \leq 999^2\). With the search space defined, the rest is make sure that all transitions are covered. Time complexity is \(O(n^2)\).

class Solution:
    def possiblyEquals(self, s1: str, s2: str) -> bool:
        N = len(s1)
        M = len(s2)

        @cache
        def dfs(i, w1, j, w2):
            if w1 > 0 and w2 > 0:
                return dfs(i, w1 - min(w1, w2), j, w2 - min(w1, w2))
            if w1 > 0 and j < M and s2[j].isalpha():
                return dfs(i, w1 - 1, j + 1, 0)
            if w2 > 0 and i < N and s1[i].isalpha():
                return dfs(i + 1, 0, j, w2 - 1)
            if w1 == 0:
                for k in range(i, min(i + 3, N)):
                    if s1[i:k+1].isdigit():
                        if dfs(k+1, int(s1[i:k+1]), j, w2):
                            return True
            if w2 == 0:
                for k in range(j, min(j + 3, M)):
                    if s2[j:k+1].isdigit():
                        if dfs(i, w1, k+1, int(s2[j:k+1])):
                            return True
            if i == N or j == M:
                return i == N and j == M and w1 == 0 and w2 == 0
            if s1[i].isalpha() and s2[j].isalpha():
                return dfs(i + 1, 0, j + 1, 0) if s1[i] == s2[j] else False
            return False

        return dfs(0, 0, 0, 0)