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.


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)
/**
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;
     }
}
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);
    }
};
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);
};
Check if an Original String Exists Given Two Encoded Strings