Given an equation, represented by words on the left side and the result on the right side.

You need to check if the equation is solvable under the following rules:


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


Return true if the equation is solvable, otherwise return false.

&nbsp;
Example 1:

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

Example 2:

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

Example 3:

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


&nbsp;
Constraints:


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


class Solution:
    def isSolvable(self, words: List[str], result: str) -> bool:
        
        # reverse words
        words = [i[::-1] for i in words]
        result = result[::-1]
        allWords = words + [result]
        
        # chars that can not be 0
        nonZero = set()
        for word in allWords:
            if len(word) > 1:
                nonZero.add(word[-1])
        
        # numbers selected in backtracking
        selected = set()
        # char to Int map
        charToInt = dict()
        mxLen = max([len(i) for i in allWords])
        
        def res(i = 0, c = 0, sm = 0):
            if c == mxLen:
                return 1 if sm == 0 else 0
            elif i == len(words):
                num = sm % 10
                carry = sm // 10
                if c >= len(result):
                    if num == 0:
                        return res(0, c+1, carry)
                    else:
                        return 0
                # result[c] should be mapped to num if a mapping exists
                if result[c] in charToInt:
                    if charToInt[result[c]] != num:
                        return 0
                    else:
                        return res(0, c+1, carry)
                elif num in selected:
                    return 0
                # if mapping does not exist, create a mapping
                elif (num == 0 and result[c] not in nonZero) or num > 0:
                    selected.add(num)
                    charToInt[result[c]] = num
                    ret = res(0, c + 1, carry)
                    del charToInt[result[c]]
                    selected.remove(num)
                    return ret
                else:
                    return 0
            else:
                word = words[i]
                if c >= len(word):
                    return res(i+1, c, sm)
                elif word[c] in charToInt:
                    return res(i+1, c, sm + charToInt[word[c]])
                else:
                    ret = 0
                    # possibilities for word[c]
                    for j in range(10):
                        if (j == 0 and word[c] not in nonZero) or j > 0:
                            if j not in selected:
                                selected.add(j)
                                charToInt[word[c]] = j
                                ret += res(i + 1, c, sm + j)
                                del charToInt[word[c]]
                                selected.remove(j)
                    return ret
        
        return res() > 0
class Solution {
     public static boolean isSolvable(String[] words, String result) {
	    // reverse all strings to facilitate add calculation.
        for (int i = 0; i < words.length; i++) {
            words[i] = new StringBuilder(words[i]).reverse().toString();
        }
        result = new StringBuilder(result).reverse().toString();
        if (!checkLength(words, result)) {
            return false;
        }
        boolean[] visited = new boolean[10];    // digit 0, 1, ..., 9
        int[] chToDigit = new int[26];
        Arrays.fill(chToDigit, -1);
        return dfs(0, 0, 0, visited, chToDigit, words, result);
    }

    /**
     * Elminate the case where result is too long
     * word1:  AAA
     * word2:  BBB
     * result: XXXXXXXXX
     */
    private static boolean checkLength(String[] words, String result) {
        int maxLen = 0;
        for (String word : words) {
            maxLen = Math.max(maxLen, word.length());
        }
        return result.length() == maxLen || result.length() == maxLen + 1;
    }

    /*
    Put all words like this:
    w1:     ABC
    w2:     EF
    w3:     GHIJ
    result: KLMNO
    i, is the row
    j,  is the column
    carrier, the one contributed from previous calculation
    chToDigit, 26 int array, which records choosen digit for 'A', 'B', 'C', ... If not choosen any, default is -1 
     */
    private static boolean dfs(int i, int j, int carrier, boolean[] visited, int[] chToDigit, String[] words, String result) {
        if (i == words.length) {
            char ch = result.charAt(j);
            // (i, i) at bottom right corner. final check
            if (j == result.length() - 1) {
                // 1. check if carrier is equal or greater than 10. If so, false.
                if (carrier >= 10) {
                    return false;
                }
                // 2. check if result.length() > 1 && result.lastCh is zero. If so the false.
                if (j > 0 && j == result.length() - 1 && chToDigit[ch - 'A'] == 0) {
                    return false;
                }
                // not selected, can select any. True.
                if (chToDigit[ch - 'A'] == -1) {
                    System.out.println(Arrays.toString(chToDigit));
                    return true;
                } else {    // if selected, check if it matches with carrier. Also, carrier can't be 0. result = '00' is invalid
                    return chToDigit[ch - 'A'] == carrier;
                }
            } else {    // reached normal result line.
                // 1. if not selected. Use current carrier's unit digit
                if (chToDigit[ch - 'A'] == -1) {
                    int selectedDigit = carrier % 10;
                    // For example carrier = 13. selectedDigit = 3. ch = 'H'. Should set 3 to 'H'.
                    // But 3 is already taken by 'B' previously. So wrong.
                    if (visited[selectedDigit]) {
                        return false;
                    }
                    visited[selectedDigit] = true;
                    chToDigit[ch - 'A'] = selectedDigit;
                    if (dfs(0, j + 1, carrier / 10, visited, chToDigit, words, result)) {
                        return true;
                    }
                    chToDigit[ch - 'A'] = -1;
                    visited[selectedDigit] = false;
                } else { // 2. selected
                    // just need to check if ch.digit equals to unit digit.
                    if (chToDigit[ch - 'A'] != carrier % 10) {
                        return false;
                    }
                    boolean ans = dfs(0, j + 1, carrier / 10, visited, chToDigit, words, result);
                    return ans;
                }
            } //
        } else { // normal word
            String word = words[i];
            // 1. check if j is equal or greater than word.len. If so pass to next word.
            if (j >= word.length()) {
                boolean ans = dfs(i + 1, j, carrier, visited, chToDigit, words, result);
                return ans;
            }
            // 2. check if it's last ch, word.len is greater than 1, and is '0'. If so false;
            if (j == word.length() - 1 && word.length() > 1 && chToDigit[word.charAt(j) - 'A'] == 0) {
                return false;
            }
            char ch = word.charAt(j);
            // 3. check if word.ch is selected. Just add current digit and move to next word.
            if (chToDigit[ch - 'A'] != -1) {
                int newSum = carrier + chToDigit[ch - 'A'];
                boolean ans = dfs(i + 1, j, newSum, visited, chToDigit, words, result);
                return ans;
            } else {
                for (int k = 0; k < visited.length; k++) {
                    if (visited[k]) {
                        continue;
                    }
                    visited[k] = true;
                    chToDigit[ch - 'A'] = k;
                    int newSum = k + carrier;
                    boolean ans = dfs(i + 1, j, newSum, visited, chToDigit, words, result);
                    if (ans) {
                        return true;
                    }
                    visited[k] = false;
                    chToDigit[ch - 'A'] = -1;
                }
            }
        }
        return false;
    }
}
class Solution {
    int limit = 0;
    unordered_map<char, int> c2i;
    unordered_map<int, char> i2c;
    bool helper(vector<string> &words, string &result, int digit, int wid, int sum)
    {
        if(digit==limit)
            return sum == 0;
        if(wid==words.size())
        {
            if(c2i.count(result[digit])==0 && i2c.count(sum%10)==0)
            {
                if(sum%10==0 && digit+1 == limit)
                    return false; //Means leading zeros
                c2i[result[digit]] = sum%10;
                i2c[sum%10] = result[digit];
                bool tmp = helper(words, result, digit+1, 0, sum/10); //0 because it will
                //go one digit at a time until all digits in words are finished
                c2i.erase(result[digit]);
                i2c.erase(sum%10);
                return tmp;
            }
            else if(c2i.count(result[digit]) && c2i[result[digit]] == sum%10) //c2i for that exits and is equal to sum%10, remember default will be 0 and sum%10 can also be 0
            {
                if(digit+1 == limit && c2i[result[digit]]==0)
                    return false; //again same condition of leading zeros
                return helper(words, result, digit+1, 0, sum/10);
            }
            else //if result[digit] exists in c2i but is not equal to sum%10
                return false;
        }
        if(digit>=words[wid].length()) //digit>current words length
            return helper(words, result, digit, wid+1, sum); //go to next word at same position
        //(digit) and sum, also going wid + 1 that is why checking wid limit in last condition already
        if(c2i.count(words[wid][digit]))
        {
            if(digit+1 == words[wid].length() && words[wid].length() > 1 && c2i[words[wid][digit]]==0)
                return false; //here we checking if there is no leading 0 in the word itself
            return helper(words, result, digit, wid+1, sum+c2i[words[wid][digit]]);
        }
        for(int i=0; i<10; i++)
        {
            if(digit+1==words[wid].length() && i==0 && words[wid].length()>1)
                continue;
            if (i2c.count(i))
                continue;
            c2i[words[wid][digit]] = i;
            i2c[i] = words[wid][digit];
            bool tmp = helper(words, result, digit, wid+1, sum+i);
            c2i.erase(words[wid][digit]);
            i2c.erase(i);
            if(tmp)
                return true;
        }
        return false;
    }
    
public:
    bool isSolvable(vector<string>& words, string result) {
        limit = result.length();
        for(auto s:words)
        {
            if(s.length()>limit)
                return false;
        }
        for(auto &s:words)
        {
            reverse(s.begin(), s.end());
        }
        reverse(result.begin(), result.end());
        return helper(words, result, 0, 0, 0);
    }
};
/**
 * @param {string[]} words
 * @param {string} result
 * @return {boolean}
 */
var isSolvable = function(words, result) {
  // set to hold all the first characters
  const firstChars = new Set();
  
  // map for steps 1 & 2
  // this will hold the key as the character and multiple as the value
  let map = {};
  for (let i = 0; i < result.length; i++) {
      const char = result[i];
      if (!i) firstChars.add(char);
      if (!map.hasOwnProperty(char)) map[char] = 0;
      map[char] -= 10 ** (result.length - i - 1);
    }
    for (let j = 0; j < words.length; j++) {
      const word = words[j];
      for (let i = 0; i < word.length; i++) {
        const char = word[i];
        if (!i) firstChars.add(char);
        if (!map.hasOwnProperty(char)) map[char] = 0;
        map[char] += 10 ** (word.length - i - 1);
      }
  }
  
  // Step 3: we group the positive and negative values
  const positives = [];
  const negatives = [];
  Object.entries(map).forEach((entry) => {
    if (entry[1] < 0) negatives.push(entry);
    else positives.push(entry);
  })

  // Step 4: backtrack
  const numsUsed = new Set();
  const backtrack = (val = 0) => {
    // if we have used all the characters and the value is 0 the input is solvable
    if (!positives.length && !negatives.length) return val === 0;
	
	// get the store that we are going to examine depending on the value
    let store = val > 0 || (val === 0 && negatives.length) ? negatives : positives;
    if (store.length === 0) return false;
    const entry = store.pop();
    const [char, multiple] = entry;
	
	// try every possible value watching out for the edge case that it was a first character
    for (let i = firstChars.has(char) ? 1 : 0; i < 10; i++) {
      if (numsUsed.has(i)) continue;
      numsUsed.add(i);
      if (backtrack(i * multiple + val)) return true;
      numsUsed.delete(i);
    }
    store.push(entry);
    return false;
  }
  return backtrack();
};
Verbal Arithmetic Puzzle