1
class Solution {
2
  int limit = 0;
3
  unordered_map<char, int> c2i;
4
  unordered_map<int, char> i2c;
5
  bool helper(vector<string> &words, string &result, int digit, int wid, int sum) {
6
    if (digit == limit) return sum == 0;
7
    if (wid == words.size()) {
8
      if (c2i.count(result[digit]) == 0 && i2c.count(sum % 10) == 0) {
9
        if (sum % 10 == 0 && digit + 1 == limit) return false; // Means leading zeros
10
        c2i[result[digit]] = sum % 10;
11
        i2c[sum % 10] = result[digit];
12
        bool tmp = helper(words, result, digit + 1, 0, sum / 10); // 0 because it will
13
        // go one digit at a time until all digits in words are finished
14
        c2i.erase(result[digit]);
15
        i2c.erase(sum % 10);
16
        return tmp;
17
      } else if (c2i.count(result[digit]) &&
18
                 c2i[result[digit]] == sum % 10) // c2i for that exits and is equal to sum%10,
19
                                                 // remember default will be 0 and sum%10 can also
20
                                                 // be 0
21
      {
22
        if (digit + 1 == limit && c2i[result[digit]] == 0)
23
          return false; // again same condition of leading zeros
24
        return helper(words, result, digit + 1, 0, sum / 10);
25
      } else // if result[digit] exists in c2i but is not equal to sum%10
26
        return false;
27
    }
28
    if (digit >= words[wid].length()) // digit>current words length
29
      return helper(words, result, digit, wid + 1,
30
                    sum); // go to next word at same position
31
    //(digit) and sum, also going wid + 1 that is why checking wid limit in last
32
    // condition already
33
    if (c2i.count(words[wid][digit])) {
34
      if (digit + 1 == words[wid].length() && words[wid].length() > 1 &&
35
          c2i[words[wid][digit]] == 0)
36
        return false; // here we checking if there is no leading 0 in the word
37
                      // itself
38
      return helper(words, result, digit, wid + 1, sum + c2i[words[wid][digit]]);
39
    }
40
    for (int i = 0; i < 10; i++) {
41
      if (digit + 1 == words[wid].length() && i == 0 && words[wid].length() > 1) continue;
42
      if (i2c.count(i)) continue;
43
      c2i[words[wid][digit]] = i;
44
      i2c[i] = words[wid][digit];
45
      bool tmp = helper(words, result, digit, wid + 1, sum + i);
46
      c2i.erase(words[wid][digit]);
47
      i2c.erase(i);
48
      if (tmp) return true;
49
    }
50
    return false;
51
  }
52

53
 public:
54
  bool isSolvable(vector<string> &words, string result) {
55
    limit = result.length();
56
    for (auto s : words) {
57
      if (s.length() > limit) return false;
58
    }
59
    for (auto &s : words) {
60
      reverse(s.begin(), s.end());
61
    }
62
    reverse(result.begin(), result.end());
63
    return helper(words, result, 0, 0, 0);
64
  }
65
};