LC 2060 [H] Check if an Original String Exists Given Two Encoded Strings - ALawliet/algorithms GitHub Wiki

this problem looks like BS. don't even bother and just give up?

have to just memorize the recursion

class Solution:
    def possiblyEquals(self, s1: str, s2: str) -> bool:    
        @lru_cache(None)
        def dfs(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 + int(s1[k])
                    k += 1
                    if dfs(k, j, diff - num):
                        return True

            elif j < len(s2) and s2[j].isdigit():
                k = j
                num = 0
                while k < len(s2) and s2[k].isdigit():
                    num = num*10 + int(s2[k])
                    k += 1
                    if dfs(i, k, diff + num):
                        return True

            elif diff == 0:
                if i < len(s1) and j < len(s2) and s1[i] == s2[j] and dfs(i+1, j+1, diff):
                    return True

            elif diff > 0:
                if i < len(s1) and dfs(i+1, j, diff - 1): 
                    return True

            elif diff < 0:
                if j < len(s2) and dfs(i, j+1, diff + 1):
                    return True

            return False
        
        return dfs(0, 0, 0)

from functools import lru_cache
class Solution:
    def possiblyEquals(self, s1: str, s2: str) -> bool:
        return self.dfs(s1, s2, 0, 0, 0)
    
    @lru_cache(None)
    def dfs(self, s1, s2, i, j, diff):
        if i == len(s1) and j == len(s2):
            return diff == 0
        if i < len(s1) and s1[i].isdigit():
            k = i
            val = 0
            while k < len(s1) and s1[k].isdigit():
                val = val*10 + int(s1[k])
                k += 1
                if self.dfs(s1, s2, k, j, diff - val):
                    return True
        elif j < len(s2) and s2[j].isdigit():
            k = j
            val = 0
            while k < len(s2) and s2[k].isdigit():
                val = val*10 + int(s2[k])
                k += 1
                if self.dfs(s1, s2, i, k, diff + val):
                    return True
        elif diff == 0:
            if i < len(s1) and j < len(s2) and s1[i] == s2[j] and self.dfs(s1, s2, i+1, j+1, diff):
                return True
        elif diff > 0:
            if i < len(s1) and self.dfs(s1, s2, i+1, j, diff - 1):
                return True
        elif diff < 0:
            if j < len(s2) and self.dfs(s1, s2, i, j+1, diff + 1):
                return True
        return False

class Solution:
    def possiblyEquals(self, s1: str, s2: str) -> bool:
        def parse(s):
            res = []
            numbers = []
            for c in s:
                if c.isdigit():
                    numbers.append(c)
                else:
                    if numbers:
                        res.append(allpossiblewildcardlengths(numbers, 0, set()))
                        numbers = []
                    res.append(c)
            if numbers:
                res.append(allpossiblewildcardlengths(numbers, 0, set()))
            return res
        
        def allpossiblewildcardlengths(nums, carryover = 0, options = set()): # generate combinations
            if len(nums) == 0:
                return
            
            for i in range(1, len(nums) + 1):
                prefix = ''.join(nums[:i])
                if i == len(nums):
                    options.add(carryover + int(prefix))
                else:
                    allpossiblewildcardlengths(nums[i:], carryover + int(prefix), options)
                    
            return options
        
        repr1 = parse(s1)
        repr2 = parse(s2)
        print(repr1) # internationlization
        print(repr2) # i{9,18}n
        
        @cache
        def dfs(i, j, diff):
            # if both strings have been exhausted, we're done
            # if only one string is at max-length, then we're probably iterating through
            # the diffs, so we can wait
            if i == len(repr1) and j == len(repr2):
                return diff == 0
            
            # if only one string has been exhausted, we're not able to match the two
            if i > len(repr1) or j > len(repr2):
                return False
            
            ei = repr1[i] if i < len(repr1) else ''
            ej = repr2[j] if j < len(repr2) else ''
            print(f'i={i} j={j} ei={ei} ej={ej}')
            
            i_wildcard = type(ei) != str
            j_wildcard = type(ej) != str
            i_str = type(ei) == str
            j_str = type(ej) == str
            
            # if one is wildcards and the other is a string
            # go through all possibilities for the wildcards and recurse
            if i_wildcard and j_str:
                for di in ei:
                    if dfs(i + 1, j, diff + di):
                        return True
                return False
            
            elif i_str and j_wildcard:
                for dj in ej:
                    if dfs(i, j + 1, diff - dj):
                        return True
                return False
            
            # if both are wildcards
            # you need to go through all the combinations
            elif i_wildcard and j_wildcard:
                for di in ei:
                    for dj in ej:
                        if dfs(i + 1, j + 1, diff + di - dj):
                            return True
                return False
            
            # if both are strings
            elif i_str and j_str:
                # if you have no wildcards, you're just checking if both strings are equivalent
                if diff == 0:
                    if ei != ej:
                        return False
                    else:
                        return dfs(i + 1, j + 1, diff)
                else:
                    # use up some wildcards
                    if diff < 0:
                        return dfs(i + 1, j, diff + 1)
                    else:
                        return dfs(i, j + 1, diff - 1)
                    
        return dfs(0, 0, 0)