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

dp(i, j, diff):

diff > 0: to match s1[i:] with s2[j:], there are diff number of char can be skipped in s1 (ie s2 use number to match char in s1)
diff < 0: to match s1[i:] with s2[j:], there are diff number of char can be skipped in s2 (ie s1 use number to match char in s2)

class Solution:
    def possiblyEquals(self, s1: str, s2: str) -> bool:
        
        @lru_cache(None)
        def dp(i, j, diff):
            if i == len(s1) and j == len(s2):
                return diff == 0

            if i < len(s1) and s1[i].isdigit():
                k = i
                num = 0
                while k < len(s1) and s1[k].isdigit():
                    num = num * 10 + ord(s1[k]) - ord('0')
                    if dp(k+1, j, diff-num):
                        return True
                    k += 1
            elif j < len(s2) and s2[j].isdigit():
                k = j
                num = 0
                while k < len(s2) and s2[k].isdigit():
                    num = num * 10 + ord(s2[k]) - ord('0')
                    if dp(i, k+1, diff+num):
                        return True
                    k += 1
            elif diff == 0:
                if i < len(s1) and j < len(s2) and s1[i] == s2[j]:
                    return dp(i+1, j+1, 0)
            elif diff > 0:
                if i < len(s1):
                    return dp(i+1, j, diff-1)
            else:
                if j < len(s2):
                    return dp(i, j+1, diff+1)
            return False
        
        return dp(0, 0, 0)

2060. Check if an Original String Exists Given Two Encoded Strings - cocoder39/coco39_LC GitHub Wiki