<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>

from functools import lru_cache

class Solution:
    def possiblyEquals(self, s1: str, s2: str) -> bool:
        curr_pos, i1, i2 = 0,0,0
        i2_num = 0

        return self.helper(s1+'a', s2+'a', 0, 0, 0, 0)
    
    @lru_cache(None)
    def helper(self, s1, s2, i1, i2, currs1, currs2):
        # print(i1, i2, currs1, currs2)
        if i1 == len(s1) and i2 == len(s2) and currs1 == currs2:
            # print("return True")
            return True
        if i1 == len(s1) and i2 == len(s2):
            return Flase
        if i1 == len(s1) or i2 == len(s2):
            return False


        # ret = False
        # if i1 == len(s1):
        #     if s2[i2] >= 'a' and s2[i2] <= 'z': # both char 
        #         ret = ret or self.helper(s1, s2, i1, i2 + 1, currs1, currs2+1);
        #     temp = 0
        #     while i2 < len(s2) and s2[i2] >= '0' and s2[i2] <= '9':
        #         num =  ord(s2[i2]) - ord('0')
        #         temp = temp * 10 + num
        #         ret = ret or self.helper(s1, s2, i1, i2 + 1, currs1, currs2 + temp)
        #         i2 += 1
        #     return ret
        # if i2 == len(s2):
        #     if s1[i1] >= 'a' and s1[i1] <= 'z': # both char 
        #         ret = ret or self.helper(s1, s2, i1 + 1, i2, currs1 + 1, currs2);
        #     temp = 0
        #     while i1 < len(s1) and s1[i1] >= '0' and s1[i1] <= '9':
        #         num =  ord(s1[i1]) - ord('0')
        #         temp = temp * 10 + num
        #         ret = ret or self.helper(s1, s2, i1+ 1, i2 , currs1 + temp , currs2)
        #         i1 += 1
        #     return ret
        

        ret = False

        if i1 < len(s1) and s1[i1].isdigit():
            #both number
            temp = 0
            k = i1
            while k < len(s1) and s1[k].isdigit(): # At most 3 times
                num =  ord(s1[k]) - ord('0')
                temp = temp * 10 + num
                ret = ret or self.helper(s1, s2, k+1, i2, currs1 + temp, currs2)
                if ret:
                    return True
                k += 1
            if ret:
                return ret
        elif s2[i2].isdigit():
            temp = 0
            k = i2
            while k < len(s2) and s2[k].isdigit(): # At most 3 times
                num =  ord(s2[k]) - ord('0')
                temp = temp * 10 + num
                ret = ret or self.helper(s1, s2, i1, k + 1, currs1, currs2 + temp)
                if ret:
                    return True
                k += 1
            if ret:
                return ret
        elif currs1 == currs2:
            if i2 < len(s2) and  i1 < len(s1) and s1[i1] == s2[i2] and self.helper(s1,s2,i1+1,i2+1, 0,0):
                return True
        elif currs1 > currs2:
            if i2 < len(s2) and self.helper(s1,s2,i1, i2+1, currs1 - currs2 - 1,0):
                return True 
        elif currs1 < currs2:
            if i1 < len(s1) and self.helper(s1, s2, i1 + 1, i2 , 0, currs2- currs1 -1):
                return True
        
                #     if currs1 > currs2:
                #         ret = ret or self.helper(s1,s2, i1, i2 + 1,currs1 - currs2 -1, 0)
                #         ret = ret or self.helper(s1,s2, i1 + 1, i2 + 1, currs1+ temp -currs2 -1,0)
                # else:
                #     ret = ret or self.helper(s1, s2, i1 + 1, i2, currs1 + temp, currs2)
                # tempb =0 
                # i3 = i2
                # while i3 < len(s2) and s2[i3] >= '0' and s2[i3] <= '9':
                #     tempb = tempb * 10 + ord(s2[i3]) - ord('0')
                #     print("a ", i1, i3,  currs1, temp, currs2, tempb)
                #     ret = ret or self.helper(s1, s2, i1 + 1, i3 + 1, currs1 + temp, currs2 + tempb)
                #     # ret = ret or self.helper(s1, s2, i1 , i3 + 1, currs1 + temp, currs2 + tempb)
                #     i3 += 1
                # i1 += 1
        # else: # s1 is a char
        #     if s2[i2] >= 'a' and s2[i2] <= 'z': # both char 
        #         if s2[i2] == s1[i1] and currs1 == currs2:
        #             ret = ret or self.helper(s1, s2, i1 + 1, i2 + 1, 0, 0)
        #     else:
        #         # s1 char, s2 number
        #         if currs2 > currs1:
        #             ret = ret or self.helper(s1, s2, i1+1, i2, 0,  currs2-1 - currs1)  
        #         if currs1 >= currs2:
        #             ret = ret or self.helper(s1, s2, i1, i2 + 1, currs1 - currs2, 0)  

        #         temp = 0
        #         while i2 < len(s2) and s2[i2] >= '0' and s2[i2] <= '9':
        #             num =  ord(s2[i2]) - ord('0')
        #             temp = temp * 10 + num
        #             ret = ret or self.helper(s1, s2, i1+1, i2+ 1, 0, currs2 + temp - currs1 -1)  
        #             i2 += 1
        return ret
1613