<p>Given an equation, represented by <code>words</code> on the left side and the <code>result</code> on the right side.</p>

<p>You need to check if the equation is solvable under the following rules:</p>

<ul>
	<li>Each character is decoded as one digit (0 - 9).</li>
	<li>No two characters can map to the same digit.</li>
	<li>Each <code>words[i]</code> and <code>result</code> are decoded as one number <strong>without</strong> leading zeros.</li>
	<li>Sum of numbers on the left side (<code>words</code>) will equal to the number on the right side (<code>result</code>).</li>
</ul>

<p>Return <code>true</code> <em>if the equation is solvable, otherwise return</em> <code>false</code>.</p>

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

<pre>
<strong>Input:</strong> words = [&quot;SEND&quot;,&quot;MORE&quot;], result = &quot;MONEY&quot;
<strong>Output:</strong> true
<strong>Explanation:</strong> Map &#39;S&#39;-&gt; 9, &#39;E&#39;-&gt;5, &#39;N&#39;-&gt;6, &#39;D&#39;-&gt;7, &#39;M&#39;-&gt;1, &#39;O&#39;-&gt;0, &#39;R&#39;-&gt;8, &#39;Y&#39;-&gt;&#39;2&#39;
Such that: &quot;SEND&quot; + &quot;MORE&quot; = &quot;MONEY&quot; ,  9567 + 1085 = 10652</pre>

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

<pre>
<strong>Input:</strong> words = [&quot;SIX&quot;,&quot;SEVEN&quot;,&quot;SEVEN&quot;], result = &quot;TWENTY&quot;
<strong>Output:</strong> true
<strong>Explanation:</strong> Map &#39;S&#39;-&gt; 6, &#39;I&#39;-&gt;5, &#39;X&#39;-&gt;0, &#39;E&#39;-&gt;8, &#39;V&#39;-&gt;7, &#39;N&#39;-&gt;2, &#39;T&#39;-&gt;1, &#39;W&#39;-&gt;&#39;3&#39;, &#39;Y&#39;-&gt;4
Such that: &quot;SIX&quot; + &quot;SEVEN&quot; + &quot;SEVEN&quot; = &quot;TWENTY&quot; ,  650 + 68782 + 68782 = 138214</pre>

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

<pre>
<strong>Input:</strong> words = [&quot;LEET&quot;,&quot;CODE&quot;], result = &quot;POINT&quot;
<strong>Output:</strong> false
<strong>Explanation:</strong> There is no possible mapping to satisfy the equation, so we return false.
Note that two different characters cannot map to the same digit.
</pre>

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

<ul>
	<li><code>2 &lt;= words.length &lt;= 5</code></li>
	<li><code>1 &lt;= words[i].length, result.length &lt;= 7</code></li>
	<li><code>words[i], result</code> contain only uppercase English letters.</li>
	<li>The number of different characters used in the expression is at most <code>10</code>.</li>
</ul>

class Solution:
    # The problem can be solved with backtracking
    # We arrange words in this manner:
    #  SEND
    #  MORE
    # MONEY
    # We will handle the question from right to left and by backtracking
    # We maintain a global hash table chartoint to temporarily store the mappings of character to integer. Initialize chartoint["A"] = -1
    # Also we maintain an inttochar array to temporarily store the inverse mapping. Initialze with inttochar[i] = "?"
    # dfs(row, col, carry) = I am at row row, column col and the carry on from before is carry
    # Rules for the dfs function:
    # 1. when col == max(len(word)): return carry == 0 (left of all columns)
    # 2. when row = len(words) + 1: # reached the answer stage, carry on must be divisible by 10  (bottom of all rows)
    # return carry % 10 == 0 and dfs(0, col+1, carry // 10)
    # Carry out the dfs function from 0, 0, 0
    # At each point, if the character we see has a negative mapping, we are free to assign for any integer i in which inttochar[i] == "?"
    # Condition to exclude leading zero: i > 0 or len(word) == 1 or col != len(word) - 1
    
    def dfs(self, row, col, carry):
        if col == self.max_word_length:
            if carry == 0:
                self.results += 1
        elif row == len(self.words):
            if carry % 10 == 0:
                self.dfs(0, col + 1, carry // 10)
        else:
            # If there is no character in the current word, skip to the next row
            word = self.words[row]
            if col >= len(word):
                self.dfs(row + 1, col, carry)
            else:
                letter, sign = word[~col], 1
                if row == len(self.words)-1:
                    sign = -1
                
                if self.char_int[letter] >= 0:
                    if self.char_int[letter] > 0 or len(word) == 1 or col != len(word) - 1:
                        self.dfs(row + 1, col, carry + sign*self.char_int[letter])
                else:
                    for i in range(10):
                        if self.int_char[i] == "?" and (i > 0 or len(word) == 1 or col != len(word)-1):
                            self.char_int[letter] = i
                            self.int_char[i] = letter
                            self.dfs(row + 1, col, carry + sign*i)
                            self.char_int[letter] = -1
                            self.int_char[i] = "?"
    
    def isSolvable(self, words: List[str], result: str) -> bool:
        alphabets = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
        self.char_int, self.int_char = {}, ["?"]*10
        self.words = words + [result]
        self.max_word_length = max([len(x) for x in self.words])
        self.results = 0
        for alphabet in alphabets:
            self.char_int[alphabet] = -1
        self.dfs(0,0,0)    
        return self.results
16500