<p>An original string, consisting of lowercase English letters, can be encoded by the following steps:</p>

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

<p>For example, <strong>one way</strong> to encode an original string <code>&quot;abcdefghijklmnop&quot;</code> might be:</p>

<ul>
	<li>Split it as a sequence: <code>[&quot;ab&quot;, &quot;cdefghijklmn&quot;, &quot;o&quot;, &quot;p&quot;]</code>.</li>
	<li>Choose the second and third elements to be replaced by their lengths, respectively. The sequence becomes <code>[&quot;ab&quot;, &quot;12&quot;, &quot;1&quot;, &quot;p&quot;]</code>.</li>
	<li>Concatenate the elements of the sequence to get the encoded string: <code>&quot;ab121p&quot;</code>.</li>
</ul>

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

<p><strong>Note</strong>: The test cases are generated such that the number of consecutive digits in <code>s1</code> and <code>s2</code> does not exceed <code>3</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

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

<p><strong class="example">Example 2:</strong></p>

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

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s1 = &quot;a5b&quot;, s2 = &quot;c5b&quot;
<strong>Output:</strong> false
<strong>Explanation:</strong> It is impossible.
- The original string encoded as s1 must start with the letter &#39;a&#39;.
- The original string encoded as s2 must start with the letter &#39;c&#39;.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

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

class Solution:
    def possiblyEquals(self, s1: str, s2: str) -> bool:
        """
        For a digit substring, we only need to find all the possible number of characters
        that it can represent.

        To build dp the trick is to use the number as length diff.
        """
        n1, n2 = len(s1), len(s2)

        def numbersof(s):
            # return the possible numbers represented by a digit sequnce
            res = set()
            # one number
            res.add(int(s))

            if len(s) == 1:
                return res

            # break the s in multiple numbers
            for k in range(1, len(s)):
                v1 = int(s[:k])
                if s[k] == '0':
                    # the next number will start with 0 - invalid
                    continue
                for v in numbersof(s[k:]):
                    res.add(v + v1)
            # print(s, res)
            return res

        # diff is the number of chars that s1 wildcards to match
        @cache
        def backtrack(i1, i2, d):
            # print(i1, i2, d)
            if i1 == n1 and i2 == n2:
                return d == 0
            
            if i1 < n1 and s1[i1].isdigit():
                # meet with a number
                d1 = i1
                while d1 < n1 and s1[d1].isdigit():
                    d1 += 1
                for v in numbersof(s1[i1:d1]):
                    if backtrack(d1, i2, d + v):
                        return True
                return False
            elif i2 < n2 and s2[i2].isdigit():
                # meet with a number
                d2 = i2
                while d2 < n2 and s2[d2].isdigit():
                    d2 += 1
                for v in numbersof(s2[i2:d2]):
                    if backtrack(i1, d2, d - v):
                        return True
                return False
            else:
                if d > 0:
                    if i2 == n2:
                        return False

                    # move i2
                    while d and i2 < n2 and not s2[i2].isdigit():
                        i2 += 1
                        d -= 1
                elif d < 0:
                    if i1 == n1:
                        return False

                    # move i1
                    while d and i1 < n1 and not s1[i1].isdigit():
                        i1 += 1
                        d += 1
                else:
                    # d == 0
                    if i1 == n1 or i2 == n2:
                        return False
                    while i1 < n1 and i2 < n2 and not s1[i1].isdigit() and not s2[i2].isdigit():
                        if s1[i1] != s2[i2]:
                            return False
                        i1 += 1
                        i2 += 1
                return backtrack(i1, i2, d)

        return backtrack(0, 0, 0)

            

        
651