var possiblyEquals = function(s1, s2) {
    // Memo array, note that we do not need to memoize true results as these bubble up
    const dp = Array.from({length: s1.length+1}, () =>
                          Array.from({length: s2.length+1},
                                     () => ([])));

    const backtrack = (p1, p2, count) => {
        if(p1 === s1.length && p2 === s2.length) return count === 0;
        // Optimization: Exit early if we have already visited here and know that it's false
        if(dp[p1][p2][count] !== undefined) return dp[p1][p2][count];

        let c1 = s1[p1];
        let c2 = s2[p2];

        // Case 1: string matches exactly
        if(p1 < s1.length && p2 < s2.length &&
           c1 === c2 && count === 0 &&
           backtrack(p1+1, p2+1, count)) return true;

        // Case 2: we can delete a character
        if(p1 < s1.length && isNaN(c1) && count < 0 &&
           backtrack(p1+1, p2, count+1)) return true;
        if(p2 < s2.length && isNaN(c2) && count > 0 &&
           backtrack(p1, p2+1, count-1)) return true;

        // Case 3: we can start stacking numbers to delete
        let num = 0;
        for(let i = 0; i < 3 && p1+i < s1.length; i++) {
            let c1 = s1[p1+i];
            if(isNaN(c1)) break;
            num = num * 10 + parseInt(c1);

            if(backtrack(p1+i+1, p2, count + num)) return true;
        }

        num = 0;
        for(let i = 0; i < 3 && p2+i < s2.length; i++) {
            let c2 = s2[p2+i];
            if(isNaN(c2)) break;
            num = num * 10 + parseInt(c2);

            if(backtrack(p1, p2+i+1, count - num)) return true;
        }

        dp[p1][p2][count] = false;
        return false;
    }

    return backtrack(0,0,0);
};
/**
Cases:

diff > 0 meaning we need to pick more chars in s1
diff < 0 meaning we need to pick more chars in s2

-1000 < diff < 1000 as there can be at most 3 digits in the string meaning largest digits are 999

1. s1[i] == s2[j] and diff = 0
    increment i+1 and j+1

2. if s1[i] is not digit and diff > 0 then increment i i+1, diff
3. if s2[j] is not digit and diff < 0 then increment j j+1, diff
4. if s1[i] is digit then get digit value and decrement diff val as we have covered such chars in the s1 string
    and increment i i+1, diff-val
5. if s2[j] is digit then get digit value and increment diff val as we need to cover such chars in the s2 string and
    increment j, j+1, diff+val

     01234
s1 = l123e
s2 = 44

i: 0
j: 0
diff: 0
    // Wildcard matching on s2[j]
    val = 4, diff = 0+4 j = 1

    i: 0
    j: 1
    diff: 4
    // Literal matching on s1[i]
    increment ith pointer as ith is a literal and we can move on to next char in s1 and decrement diff

        i: 1
        j: 1
        diff: 3
        // Wildcard matching on s1[i]
        val = 1 diff = 3-1 = 2 increment i

            i: 2
            j: 1
            diff: 2
            // Wildcard matching on s1[i]
            val = 2 diff = 2-2 = 0 increment i

                i: 3
                j: 1
                diff: 0
                // Wildcard matching on s1[i]
                val=3 diff = 0-3 = -3, increment i

                    i: 4
                    j: 1
                    diff: -3
                    // Wildcard matching on s2[j]
                    val = 4 diff = -3+4 =1 increment j

                        i: 4
                        j: 2
                        diff: 1
                         // Literal matching on s1[i]
                         decrement i-1 and increment i

                            i=5
                            j=2
                                diff==0 return true
                        dp[4][2][1] = true
                        return true
                    return dp[4][1][1000-3] = true
                return dp[3][1][0] = true

            i: 2
            j: 1
            diff: 2
            return dp[2][1][2] = true
            return true

        i: 0
        j: 1
        diff: 4
        return dp[0][1][4] = true
    return true
*/

class Solution {
    //112ms
     public boolean possiblyEquals(String s1, String s2) {
         return helper(s1.toCharArray(), s2.toCharArray(), 0, 0, 0, new Boolean[s1.length()+1][s2.length()+1][2001]);
     }

     boolean helper(char[] s1, char[] s2, int i, int j, int diff, Boolean[][][] dp) {
         if(i == s1.length && j == s2.length) {
             return diff == 0;
         }

         if(dp[i][j][diff+1000] != null)
             return dp[i][j][diff+1000];

         // if both i and j are at the same location and chars are same then simply increment both pointers
         if(i < s1.length && j < s2.length && diff == 0 && s1[i] == s2[j]) {
             if(helper(s1, s2, i+1, j+1, diff, dp)) {
                 return dp[i][j][diff+1000] = true;
             }
         }

         // if s1[i] is literal and diff > 0 then increment i and decrement diff by 1
         if(i < s1.length && !Character.isDigit(s1[i]) && diff > 0 && helper(s1, s2, i+1, j, diff-1, dp)) {
             return dp[i][j][diff+1000] = true;
         }

         // if s2[j] is literal and diff < 0 then increment j and increment diff by 1
         // as we are done with the current jth char
         if(j < s2.length && !Character.isDigit(s2[j]) && diff < 0 && helper(s1, s2, i, j+1, diff+1, dp)) {
             return dp[i][j][diff+1000] = true;
         }

         // wildcard matching in s1
         // if s1 contains l123
         // then need to check with val as 1 then val as 12 and val as 123
         for(int k = i, val = 0; k < i + 4 && k < s1.length && Character.isDigit(s1[k]); k++) {
             val = val * 10 + s1[k] -'0';
             if(helper(s1, s2, k+1, j, diff-val, dp)) {
                 return dp[i][j][diff+1000] = true;
             }
         }

         // wildcard matching in s2
         // if s2 contains l123
         // then need to check with val as 1 then val as 12 and val as 123
         for(int k = j, val = 0; k < j + 4 && k < s2.length && Character.isDigit(s2[k]); k++) {
             val = val * 10 + s2[k] -'0';
             if(helper(s1, s2, i, k+1, diff+val, dp)) {
                 return dp[i][j][diff+1000] = true;
             }
         }

         return dp[i][j][diff+1000] = false;
     }
}
Check if an Original String Exists Given Two Encoded Strings
from functools import lru_cache
class Solution:
    def possiblyEquals(self, s1: str, s2: str) -> bool:

        def getValidPrefixLength(s,start):
            end = start
            while end < len(s) and s[end].isdigit(): end += 1
            return end

        @lru_cache(None)
        def possibleLengths(s):
            """Return all possible lengths represented by numeric string s."""
            ans = {int(s)}
            for i in range(1, len(s)):
                # add all lengths by splitting numeric string s at i
                ans |= {x+y for x in possibleLengths(s[:i]) for y in possibleLengths(s[i:])}
            return ans

        @lru_cache(None)
        def dp(i, j, diff):
            """Return True if s1[i:] matches s2[j:] with given differences."""

            # If both have reached end return true if none of them are leading
            if i == len(s1) and j == len(s2): return diff == 0

            # s1 has not reached end and s1 starts with a digit
            if i < len(s1) and s1[i].isdigit():
                i2 = getValidPrefixLength(s1,i)
                for L in possibleLengths(s1[i:i2]):
                    # substract since lead of s2 decreases by L
                    if dp(i2, j, diff-L): return True

            # s2 has not reached end and s2 starts with a digit
            elif j < len(s2) and s2[j].isdigit():
                j2 = getValidPrefixLength(s2,j)
                for L in possibleLengths(s2[j:j2]):
                    # add since lead of s2 increase by L
                    if dp(i, j2, diff+L): return True

            # if none of them have integer prefix or a lead over the other
            elif diff == 0:
                # if only one of them has reached end or current alphabets are not the same
                if i == len(s1) or j == len(s2) or s1[i] != s2[j]: return False
                # skip same alphabets
                return dp(i+1, j+1, 0)

            # if none of them have integer prefix & s2 lead over s1
            elif diff > 0:
                # no s1 to balance s2's lead
                if i == len(s1): return False
                # move s1 pointer forward and reduce diff
                return dp(i+1, j, diff-1)

            # if none of them have integer prefix & s1 lead over s2
            else:
                # no s2 to balance s1's lead
                if j == len(s2): return False
                # move s2 pointer forward and increase diff
                return dp(i, j+1, diff+1)

        # start with starts of both s1 and s2 with no lead by any of them
        return dp(0, 0, 0)
An original string, consisting of lowercase English letters, can be encoded by the following steps:


	Arbitrarily split it into a sequence of some number of non-empty substrings.
	Arbitrarily choose some elements (possibly none) of the sequence, and replace each with its length (as a numeric string).
	Concatenate the sequence as the encoded string.


For example, one way to encode an original string "abcdefghijklmnop" might be:


	Split it as a sequence: ["ab", "cdefghijklmn", "o", "p"].
	Choose the second and third elements to be replaced by their lengths, respectively. The sequence becomes ["ab", "12", "1", "p"].
	Concatenate the elements of the sequence to get the encoded string: "ab121p".


Given two encoded strings s1 and s2, consisting of lowercase English letters and digits 1-9 (inclusive), return true if there exists an original string that could be encoded as both s1 and s2. Otherwise, return false.

Note: The test cases are generated such that the number of consecutive digits in s1 and s2 does not exceed 3.

&nbsp;
Example 1:

Input: s1 = "internationalization", s2 = "i18n"
Output: true
Explanation: It is possible that "internationalization" was the original string.
- "internationalization" 
  -&gt; Split:       ["internationalization"]
  -&gt; Do not replace any element
  -&gt; Concatenate:  "internationalization", which is s1.
- "internationalization"
  -&gt; Split:       ["i", "nternationalizatio", "n"]
  -&gt; Replace:     ["i", "18",                 "n"]
  -&gt; Concatenate:  "i18n", which is s2


Example 2:

Input: s1 = "l123e", s2 = "44"
Output: true
Explanation: It is possible that "leetcode" was the original string.
- "leetcode" 
  -&gt; Split:      ["l", "e", "et", "cod", "e"]
  -&gt; Replace:    ["l", "1", "2",  "3",   "e"]
  -&gt; Concatenate: "l123e", which is s1.
- "leetcode" 
  -&gt; Split:      ["leet", "code"]
  -&gt; Replace:    ["4",    "4"]
  -&gt; Concatenate: "44", which is s2.


Example 3:

Input: s1 = "a5b", s2 = "c5b"
Output: false
Explanation: It is impossible.
- The original string encoded as s1 must start with the letter 'a'.
- The original string encoded as s2 must start with the letter 'c'.


&nbsp;
Constraints:


	1 &lt;= s1.length, s2.length &lt;= 40
	s1 and s2 consist of digits 1-9 (inclusive), and lowercase English letters only.
	The number of consecutive digits in s1 and s2 does not exceed 3.


class Solution {
public:
    bool memo[50][50][2000];
    bool comp_seqs(string& s1, string& s2, int i1, int i2, int diff){
        // check true condition
        if(i1 == s1.size() && i2 == s2.size())
            return diff == 0;
        // add 1000 to 'diff' be in range [0, 2000)
        bool& ret = memo[i1][i2][diff+1000];
        if(ret)
            return false; // immediately return
        ret = true; // check visited

        // diff > 0 or diff < 0 checking to ensure the diff always be in range (-1000, 1000)
        // in the case that s1[i1] is a digit
        if(diff >= 0 && i1 < s1.size() && s1[i1] <= '9'){
            int num1 = 0;
            for(int i=0; i<min(3, (int)s1.size()-i1); i++){ // loop maximum 3 consecutive digits
                if(s1[i1 + i] > '9')
                    break;
                num1 = num1*10 + s1[i1 + i] - '0';
                if(comp_seqs(s1, s2, i1+i+1, i2, diff-num1))
                    return true;
            }
        }else if(diff <= 0 && i2 < s2.size() && s2[i2] <= '9'){ // in the case that s2[i2] is a digit
            int num2 = 0;
            for(int i=0; i<min(3, (int)s2.size()-i2); i++){
                if(s2[i2 + i] > '9')
                    break;
                num2 = num2*10 + s2[i2 + i] - '0';
                if(comp_seqs(s1, s2, i1, i2+i+1, diff+num2))
                    return true;
            }
        }else if(diff == 0){
            if(i1 >= s1.size() || i2 >= s2.size() || s1[i1] != s2[i2]) // reject infeasible cases
                return false;
            return comp_seqs(s1, s2, i1+1, i2+1, 0);
        }else if(diff > 0){
            if(i1 >= s1.size()) // reject infeasible cases
                return false;
            return comp_seqs(s1, s2, i1+1, i2, diff - 1);
        }else{
            if(i2 >= s2.size()) // reject infeasible cases
                return false;
            return comp_seqs(s1, s2, i1, i2+1, diff + 1);
        }
        return false;
    }
    bool possiblyEquals(string s1, string s2) {
        return comp_seqs(s1, s2, 0, 0, 0);
    }
};