1307. Verbal Arithmetic Puzzle
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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| class Solution {
unordered_map<char,int> mp;
unordered_map<int, char> rmp;
bool helper(vector<string>& w, string& res, int pos, int idx, int carry) {
if(pos == res.length()) return carry == 0;
if(idx == w.size()) {
if(!mp.count(res[pos]) and !rmp.count(carry % 10)) {
if(carry % 10 == 0 and pos + 1 == res.length()) return false;
mp[res[pos]] = carry % 10;
rmp[carry%10] = res[pos];
if(helper(w,res,pos + 1, 0, carry / 10)) return true;
mp.erase(res[pos]);
rmp.erase(carry%10);
return false;
}
if(mp.count(res[pos]) and mp[res[pos]] == carry % 10) {
if(pos + 1 == res.length() and mp[res[pos]] == 0) return false;
return helper(w,res,pos + 1, 0, carry / 10);
}
return false;
}
if(pos >= w[idx].length()) return helper(w,res,pos,idx + 1, carry);
if(mp.count(w[idx][pos])) {
if(pos + 1 == w[idx].length() and w[idx].length() > 1 and mp[w[idx][pos]] == 0) return false;
return helper(w,res,pos,idx + 1, carry + mp[w[idx][pos]]);
}
for(int i = 0; i < 10; i++) {
if(pos + 1 == w[idx].length() and i == 0 and w[idx].length() > 1) continue;
if(rmp.count(i)) continue;
mp[w[idx][pos]] = i;
rmp[i] = w[idx][pos];
if(helper(w,res,pos,idx+1,carry + i)) return true;
mp.erase(w[idx][pos]);
rmp.erase(i);
}
return false;
}
public:
bool isSolvable(vector<string>& words, string res) {
for(auto& w : words) {
if(w.length() > res.length()) return false;
reverse(begin(w), end(w));
}
reverse(begin(res), end(res));
return helper(words, res, 0, 0, 0);
}
};
|
