<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:
        def parse_int(s: str, i: int) -> Iterator[tuple[int, int]]:
            """
            Incrementally parses an integer starting from s[i].

            Example:
            "456" is parsed as (4,1), (45,2), and (456,3)

            :param s: string to parse
            :param i: index to start parsing from
            :return: the integer and its length (number of digits)
            """
            n = 0
            j = i
            while j < len(s) and s[j].isdigit():
                n = n * 10 + int(s[j])
                j += 1
                yield n, j - i

        @functools.cache
        def dfs(i: int, j: int, skip: int) -> bool:
            """
            Checks if two encoded strings s1 and s2 are equal in length after decoding.
            The algorithm works similar to digit by digit addition. 
            The parameter skip is analogous to the carry that indicates how many characters can be skipped from one of the strings.
            - If s1[i] or s2[j] is a digit, then we try with increasing lengths of integers, which is combined with skip to produce the new value.
            - If neither of s1[i] and s2[j] is a digit, and skip is not zero, then we skip the respective characters from s1 or s2.
            - If neither of s1[i] and s2[j] is a digit, and skip is zero, then s1[i] must be equal to s2[j] for the strings to be equal in length.

            Example:
            s1="a3e", s2="ab21".
            Indices with asterisk indicate that it is _not_ incremented in the current iteration.

            +----+----+-------+-------+----------------------------------+
            | i  | j  | s1[i] | s2[j] | skip (at the start of iteration) |
            +----+----+-------+-------+----------------------------------+
            | 0  | 0  | 'a'   | 'a'   |                                0 |
            | 1  | 1* |  3    | 'b'   |                                0 |
            | 2* | 1  | 'e'   | 'b'   |                               -3 |
            | 2* | 2  | 'e'   |  2    |                               -2 |
            | 2* | 3  | 'e'   |  1    |                                0 |
            | 2  | 4* | 'e'   |  ---  |                                1 |
            | 3  | 4  | ---   |  ---  |                                0 |
            +----+----+-------+-------+----------------------------------+

            Note that how skip=-2 and s2[2]=2 are combined to produce skip=0 in the 5th iteration.

            :param i: index into string s1
            :param j: index into string s2
            :param skip: number of characters to skip; if positive, skip from s1, if negative skip from s2
            :return: true if the decoded strings are equal in length, false otherwise
            """
            if i == len(s1) and j == len(s2):
                return skip == 0
            if i < len(s1) and s1[i].isdigit():
                return any(dfs(i + k, j, skip - n) for n, k in parse_int(s1, i))
            elif j < len(s2) and s2[j].isdigit():
                return any(dfs(i, j + k, skip + n) for n, k in parse_int(s2, j))
            elif skip == 0 and i < len(s1) and j < len(s2):
                return s1[i] == s2[j] and dfs(i + 1, j + 1, skip)
            elif skip > 0 and i < len(s1):
                return dfs(i + 1, j, skip - 1)
            elif skip < 0 and j < len(s2):
                return dfs(i, j + 1, skip + 1)
            return False
            
        return dfs(0, 0, 0)
957