Problem Explanation:

This is a problem about mapping numbers to words, similar to the classic problem of cryptarithms where mathematical expressions involve letters instead of actual numbers. The idea is to assign each letter in the words and the result a unique digit, form numbers by these assignments, and check if the equality is maintained. In all these assignments, no leading zeroes are allowed, i.e., no word can start with a zero.

For example, with words = ["SEND", "MORE"] and result = "MONEY", we can assign 'S'-> 9, 'E'->5, 'N'->6, 'D'->7, 'M'->1, 'O'->0, 'R'->8, 'Y'->'2'. This forms: `"SEND"(9567) + "MORE"(1085) = "MONEY"(10652), which is a valid equation.

Solution Approach:

The solution uses depth-first search (DFS) to fill the paths from all digits (0-9), tracking the ones already used. At each step, we check the current position in all words and the resulting word. We start from the least significant positions, i.e., from the rightmost characters, and go to the leftmost characters.

For each remaining character in this column for each word, we either fill in a digit that has not been used before, or if this character has been assigned a digit before, we just continue to the next character.

If we have looked at all the characters in this column for all the words, we then check if the sum of the assigned digits for this column matches the digit in the corresponding result column. If yes, we continue to the next column; if not, we stop and backtrack.

Let's walk through this in the example words = ["SEND", "MORE"] and result = "MONEY":

1. Start with the rightmost column, 'D' in 'SEND' and 'E' in 'MORE'. Let's assign 'D' -> 7 and 'E' -> 5.
2. Next, the 'N' in 'SEND' and 'R' in 'MORE'. We assign 'N' -> 6 and 'R' -> 8.
3. For the third column, 'E' in 'SEND' has been assigned, then we assign 'O' in 'MORE' -> 0, 'S' in 'SEND' -> 9, 'M' in 'MORE' -> 1.
4. The last column 'M' in 'MONEY' -> 1.
5. Since 'S', 'E', 'N', 'D', 'M', 'O', 'R', 'Y' in 'MONEY' have all been assigned and the formed numbers give a valid equation, we stop and return True.

C++ Solution:

1
2cpp
3class Solution {
4 public:
5  bool isSolvable(vector<string>& words, string result) {
6    vector<bool> usedDigit(10);
7    words.push_back(result);
8    int rows = words.size();
9    int cols = 0;
10    for (const string& word : words) cols = max(cols, int(word.length()));
11    return dfs(words, 0, 0, 0, cols, usedDigit);
12  }
13
14  bool dfs(vector<string>& words, int row, int col, int sum, const int cols, vector<bool>& usedDigit) {
15    unordered_map<char, int> letterToDigit;
16
17    if (col == cols) return sum == 0;
18    if (row == rows) return sum % 10 == 0 && dfs(words, 0, col + 1, sum / 10, cols, usedDigit);
19
20    string word = words[row];
21    if (col >= word.length()) return dfs(words, row + 1, col, sum, cols, usedDigit);
22
23    char letter = word[word.length() - col - 1];
24    int sign = row == rows - 1 ? -1 : 1;
25
26    if (const auto it = letterToDigit.find(letter); it != letterToDigit.end() && (it->second > 0 || col < word.length() - 1))
27      return dfs(words, row + 1, col, sum + sign * letterToDigit[letter], cols,  usedDigit);
28
29    for (int digit = 0; digit < 10; ++digit)
30      if (!usedDigit[digit] && (digit > 0 || col + 1 < word.length())) {
31        letterToDigit[letter] = digit;
32        usedDigit[digit] = true;
33        if (dfs(words, row + 1, col, sum + sign * digit, cols,  usedDigit)) return true;
34        usedDigit[digit] = false;
35        letterToDigit.erase(letter);
36      }
37
38    return false;
39  }
40};

Note:

Due to the time constraint, solutions in other languages could not be provided.# Python Solution:

1
2python
3class Solution:
4    def isSolvable(self, words, result):
5        n = max(map(len, words + [result]))
6        words = [word.rjust(n, '#') for word in words]
7        result = result.rjust(n, '#')
8        
9        used = [0]*10
10        dict_ = {}
11        self.words = words
12        self.result = result
13        return self.dfs(n-1, 0, used, dict_)
14        
15    def dfs(self, i, carry, used, dict_):
16        m, n = len(self.words), len(self.result)
17        if i < 0:
18            return carry == 0
19        
20        s = carry
21        for j in range(m):
22            if self.words[j][i] == '#': continue
23            if self.words[j][i] not in dict_:
24                for k in range(10):
25                    if used[k]: continue
26                    if self.words[j][i-1] != '#' and k == 0: continue
27                    dict_[self.words[j][i]] = k
28                    used[k] = 1
29                    s += dict_[self.words[j][i]]
30                    if self.dfs(i-1, s//10, used, dict_): return True
31                    s -= dict_[self.words[j][i]]
32                    used[k] = 0
33                    del dict_[self.words[j][i]]
34                return False
35            
36            s += dict_[self.words[j][i]]
37        
38        if self.result[i] not in dict_:
39            if used[s%10] or (self.result[i-1] != '#' and s%10 == 0): return False
40            dict_[self.result[i]] = s%10
41            used[s%10] = 1
42            if self.dfs(i-1, s//10, used, dict_): return True
43            used[s%10] = 0
44            del dict_[self.result[i]]
45            return False
46        
47        return s%10 == dict_[self.result[i]] and self.dfs(i-1, s//10, used, dict_)
48
49
50# Test the solution
51words = ["SEND", "MORE"]
52result = "MONEY"
53sol = Solution()
54print(sol.isSolvable(words, result))  # Should print True

JavaScript Solution

1
2javascript
3var isSolvable=function(words, result) {
4    const map = new Map()
5    const used = new Set()
6    const isFirst = new Set()
7    for (let word of words.concat([result])) for (let i = 0; i < word.length; ++i) {
8        if (i === 0 && word.length > 1) isFirst.add(word[i])
9        if (!map.has(word[i])) map.set(word[i], [])
10        map.get(word[i]).push([words.indexOf(word), word.length - 1 - i])
11    }
12    words = words.map(word => [...word].reverse().join(''))
13
14    result = [...result].reverse().join('')
15    const dfs = (str, i, sum) => {
16        if (i === 10) return sum === 0
17        if (sum % (1 << 10) != (str[i] || 0) - '0'.charCodeAt()) return false
18        if (i === str.length) return sum === 0
19        for (let j = (isFirst.has(result[i]) ? 1 : 0); j < 10; ++j) {
20            if (used.has(j)) continue
21            const next = []
22            let carry = sum >> 10
23            for (let [idx, exp] of map.get(result[i]) || []) {
24                if (words[idx][exp] === undefined) next.push(j << exp)
25                else {
26                    if ((carry & 1) != (words[idx][exp].charCodeAt() + j >> exp & 1)) return false
27                    words[idx] = words[idx].substring(0, exp) + String.fromCharCode((words[idx][exp].charCodeAt() + j >> exp) % 10 + '0'.charCodeAt()) + words[idx].substring(exp + 1)
28                }
29                carry >>= 1
30            }
31            next.push(j << i)
32            used.add(j)
33            if (dfs(str, i + 1, sum + (carry << 10) + next.reduce((a, b) => a + b, 0))) return true
34            used.delete(j)
35            for (let k = next.length - 1; k >= 0; --k) {
36                let [idx, exp] = map.get(result[i])[k] || []
37                if (words[idx] === undefined) continue
38                words[idx] = words[idx].substring(0, exp) + String.fromCharCode((words[idx].substring(exp, exp + 1).charCodeAt() + 10 - j % 10) % 10 + '0'.charCodeAt()) + words[idx].substring(exp + 1)
39            }
40        }
41        return false
42    }
43    return dfs(result, 0, 0)
44};
45
46words = ["ACCA", "DDA"];
47result = "ADDC";
48console.log(words, result, isSolvable(words, result));

Solution Implementation