<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:
        # memory = {signature : True/False}
        # A signature is a representation of two strings and its compare condition
        memory = {}
        
        def getSignature(s1, s2, s1fixedlen) -> str:
            if s1fixedlen > 0:
                mysignature = s1 + '-' + s2 + '-' + str(s1fixedlen)
            else:
                if s1 <= s2:
                    mysignature = s1 + '-' + s2 + '-0'
                else:
                    mysignature = s2 + '-' + s1 + '-0'
                    
            return mysignature
                    
            
        def myCompare(s1, s2, s1fixedlen) -> bool:
            if not s1:
                if s2:
                    return False
                else:
                    return True
            elif not s2:
                return False
            
            mysignature = getSignature(s1, s2, s1fixedlen)
            if mysignature in memory:
                return memory[mysignature]
            
            if s1fixedlen > 0:
                if s1fixedlen == 1:
                    d = ord(s1[0])-ord('0')
                    subs1 = s1[1:]
                elif s1fixedlen == 2:
                    d = int(s1[:2])
                    subs1 = s1[2:]
                else:
                    d = int(s1[:3])
                    subs1 = s1[3:]
                    
                if s2[0].isdigit():
                    d2 = ord(s2[0])-ord('0')
                    if d>d2:
                        #news1fixedlen = s1fixedlen
                        if d-d2<10:
                            news1fixedlen = 1
                        elif d-d2<100:
                            news1fixedlen = 2
                        else:
                            news1fixedlen = 3
                        newsubs1 = str(d-d2)+subs1
                        onepath = myCompare(newsubs1, s2[1:], news1fixedlen)
                        if onepath:
                            memory[mysignature] = True
                            return True
                    elif d<d2:
                        newsubs2 = str(d2-d)+s2[1:]
                        onepath = myCompare(newsubs2, subs1, 1)
                        if onepath:
                            memory[mysignature] = True
                            return True
                    else:
                        onepath = myCompare(subs1, s2[1:], 0)
                        if onepath:
                            memory[mysignature] = True
                            return True
                            
                    if len(s2)>1 and s2[1].isdigit():
                        d2 = int(s2[:2])
                        if d>d2:
                            #news1fixedlen = s1fixedlen
                            if d-d2<10:
                                news1fixedlen = 1
                            elif d-d2<100:
                                news1fixedlen = 2
                            else:
                                news1fixedlen = 3
                            newsubs1 = str(d-d2)+subs1
                            onepath = myCompare(newsubs1, s2[2:], news1fixedlen)
                            if onepath:
                                memory[mysignature] = True
                                return True
                        elif d<d2:
                            newsubs2 = str(d2-d)+s2[2:]
                            #news2fixedlen = 2
                            if d2-d<10:
                                news2fixedlen = 1
                            else:
                                news2fixedlen = 2
                            onepath = myCompare(newsubs2, subs1, news2fixedlen)
                            if onepath:
                                memory[mysignature] = True
                                return True
                        else:
                            onepath = myCompare(subs1, s2[2:], 0)
                            if onepath:
                                memory[mysignature] = True
                                return True
                            
                        if len(s2)>2 and s2[2].isdigit():
                            d2 = int(s2[:3])
                            if d>d2:
                                #news1fixedlen = s1fixedlen
                                if d-d2<10:
                                    news1fixedlen = 1
                                elif d-d2<100:
                                    news1fixedlen = 2
                                else:
                                    news1fixedlen = 3
                                newsubs1 = str(d-d2)+subs1
                                onepath = myCompare(newsubs1, s2[3:], news1fixedlen)
                                if onepath:
                                    memory[mysignature] = True
                                    return True
                            elif d<d2:
                                newsubs2 = str(d2-d)+s2[3:]
                                #news2fixedlen = 2
                                if d2-d<10:
                                    news2fixedlen = 1
                                elif d2-d<100:
                                    news2fixedlen = 2
                                else:
                                    news2fixedlen = 3
                                onepath = myCompare(newsubs2, subs1, news2fixedlen)
                                if onepath:
                                    memory[mysignature] = True
                                    return True
                            else:
                                onepath = myCompare(subs1, s2[3:], 0)
                                if onepath:
                                    memory[mysignature] = True
                                    return True
                            
                else: #s2 starts with a letter
                    j = 0
                    while d>0 and j<len(s2):
                        if s2[j].islower():
                            d -= 1
                            j += 1
                        else:
                            break
                        
                    if d>0 and j<len(s2):
                        #news1fixedlen = s1fixedlen
                        if d<10:
                            news1fixedlen = 1
                        elif d<100:
                            news1fixedlen = 2
                        else:
                            news1fixedlen = 3
                        newsubs1 = str(d)+subs1
                        onepath = myCompare(newsubs1, s2[j:], news1fixedlen)
                        if onepath:
                            memory[mysignature] = True
                            return True
                    elif d>0:
                        memory[mysignature] = False
                        return False
                    else: # d is fully consumed
                        onepath = myCompare(subs1, s2[j:], 0)
                        if onepath:
                            memory[mysignature] = True
                            return True
            else: #s1fixedlen == 0
                if s1[0].isdigit():
                    onepath = myCompare(s1, s2, 1)
                    if onepath:
                        memory[mysignature] = True
                        return True
                    if len(s1)>1 and s1[1].isdigit():
                        onepath = myCompare(s1, s2, 2)
                        if onepath:
                            memory[mysignature] = True
                            return True
                        if len(s1)>2 and s1[2].isdigit():
                            onepath = myCompare(s1, s2, 3)
                            if onepath:
                                memory[mysignature] = True
                                return True
                elif s2[0].isdigit():
                    onepath = myCompare(s2, s1, 1)
                    if onepath:
                        memory[mysignature] = True
                        return True
                    if len(s2)>1 and s2[1].isdigit():
                        onepath = myCompare(s2, s1, 2)
                        if onepath:
                            memory[mysignature] = True
                            return True
                        if len(s2)>2 and s2[2].isdigit():
                            onepath = myCompare(s2, s1, 3)
                            if onepath:
                                memory[mysignature] = True
                                return True
                else: # both s1 and s2 start with letter
                    i = 0
                    minlen = min(len(s1), len(s2))
                    while i < minlen:
                        if s1[i].isdigit() or s2[i].isdigit():
                            onepath = myCompare(s1[i:], s2[i:], 0)
                            if onepath:
                                memory[mysignature] = True
                                return True
                            else:
                                memory[mysignature] = False
                                return False
                        elif s1[i] != s2[i]:
                            memory[mysignature] = False
                            return False
                        i += 1
                        
                    if len(s1) == len(s2):
                        memory[mysignature] = True
                        return True
                    else:
                        memory[mysignature] = False                        
                        return False
            
            memory[mysignature] = False
            return False
        
        #myresult = myCompare(s1, s2, 0)
        myresult = myCompare(s1, s2, 0)
        return myresult

"""
Test Case #213 result is wrong:
"879w788w777w"
"999w988w988w"
Expected True
But actually it is False

By carefully trimming the left and right, we see contraditory results by the platform:
"79w788w76"
"199w988w98"
Expected: True (actually should be False)

"9w788w76"
"129w988w98"
Expected: True (actually should be False)

"8w788w76"
"29w988w98"
Expected: False (this is correct. This shows that s2 compression is not using the signle digit 1.)

"788w76"
"119w988w98"
Expected: True (this is correct if using 3 digits 129 for compression. This shows that s2 compression is not using all the 3 digits 129.)!!!!!

"w788w76"
"39w988w98"
Expected: True (True is correct, but using 39 as a whole not 3 and 9 seperately. This using-as-a-whole path, as shown below, cannot be reached from the whole strings. So the result from this branch is invalid.)

"788w76"
"38w988w98"
Expected: True (True is correct. This is the reduction from using-39-as-a-whole; this path cannot be reached from the whole strings. So the result from this branch is invalid.)

"788w76"
"29w988w98"
Expected: False (False is correct, this is the only path viable to reach from the whole strings. Therefore the correct answer to the case is False.)
"""
1416