# 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).
• Every pair of different characters must map to different digits.
• 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`.

Example 1:

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

Example 2:

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

Example 3:

``````Input: words = ["LEET","CODE"], result = "POINT"
Output: false
``````

Constraints:

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

``````class Solution {
public:
bool isSolvable(vector<string>& words, string result) {
unordered_set<char> charSet;
int charCnt[91] = {};
for (string word : words) {
int n = word.size();
for (int i = 0; i < n; ++i) {
if (i == 0 && n > 1) nonLeadingZero[word[i]] = true;
charSet.insert(word[i]);
charCnt[word[i]] += pow(10, n - 1 - i);
}
}
int n = result.size();
for (int i = 0; i < n; ++i) {
if (i == 0 && n > 1) nonLeadingZero[result[i]] = true;
charSet.insert(result[i]);
charCnt[result[i]] -= pow(10, n - 1 - i);
}
bool used[10] = {};
char charList[charSet.size()];
int i = 0;
for (char c : charSet) {
charList[i++] = c;
}
return dfs(charList, charCnt, 0, 0, nonLeadingZero, used, i);
}
bool dfs(char* charList, int* charCnt, int cur, int sum, bool* nonLeadingZero, bool* used, int numChars) {
if (cur == numChars) return sum == 0;
for (int i = 0; i <= 9; ++i) {
char c = charList[cur];
if (used[i] || (i == 0 && nonLeadingZero[charList[cur]])) continue;
used[i] = true;
if (dfs(charList, charCnt, cur + 1, sum + charCnt[charList[cur]] * i, nonLeadingZero, used, numChars)) return true;
used[i] = false;
}
return false;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1307

https://leetcode.com/problems/verbal-arithmetic-puzzle/

https://leetcode.com/problems/verbal-arithmetic-puzzle/discuss/463916/C%2B%2B-12ms-DFS-and-Backtracking-and-Prunning-Strategy

https://leetcode.com/problems/verbal-arithmetic-puzzle/discuss/463953/Java-Fast-Backtracking-Clean-Code-O(n!)-~-300ms

LeetCode All in One 题目讲解汇总(持续更新中…)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation