[LeetCode] 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.

这道题给了一个等式，左边是一系列的单词，右边是一个结果字符串（也是一个单词），每个字母代表一个 [0, 9] 中的数字，问该等式是否有解。题目中还给了一些限定条件，比如说字符均为大写字母，不同的字母具有不同的值。每个单词解码成的数字不能有 leading zero，即两位数以上的开头位不能是0。还有一个条件是，左边所有的单词解码成的数字之和等于右边的结果字符串解码成的数字。由上述的条件可以推断出等式中不同的字母个数不超过 10 个，不然就无法满足一对一的映射关系，实际上就是解一个多元一次方程，稍有不同的就是这里的变量与变量之间是高低位的关系，比如 xyz 的计算方法是 100*x + 10*y + z。

既然是解方程，至少要知道变量都有哪些吧，这里用一个 HashSet 来保存所有的字母。接下来需要计算每一个变量的系数，只要知道某个变量在整数中的哪一位，就可以算出系数，是 10 的倍数，又因为变量在不同的整数中的位数不同，所以要把所有的系数都累加起来。由于等式左右两边的系数是可以抵消的，所以左边的系数用加，右边的系数用减就可以了。这里用个数组 charCnt 来统计每个字母的系数，大小初始化为 91，因为大写字母从A到Z的 ASCII 码是在 [65, 90] 的范围内。另外题目中还说了多位数的最高位不能是0，所以要标记一下每个长度大于1的单词的首字母，之后不能将其赋值为0。

搞清楚了以上内容，就可以开始写代码了，遍历给定的 words 数组，对于每一个单词 word，遍历每一个位置上的字母，对于首个字母，在 nonLeadingZero 中标记为 true，并把每一个字母都加入到 charSet 中，根据当前的位置计算其位置权重，用 pow 函数可以计算出系数，加到 charCnt 中该字母的总系数上。类似的方法对 result 字符串进行处理，标记首字母，加入 charSet 中，不同的是计算系数是用减法，原因在前面的分析中已经解释了。有了每个变量的系数，现在就要找变量的值了，由于减去了所有等式右边的系数，则等式右边为0了，所以只要找到一组变量的解，使其各自乘以其系数，相加为0即可。没有太好的方法，只能遍历所有的情况，用递归来实现。这里先把 charSet 转为一个数组，大小为 10 即可，因为前面分析过不同字母的个数不会超过 10 个。

在递归函数中，首先判断当前解析到的变量的位置 cur 是否已经等于变量总个数了，是的话表示所有变量都解析完了，然后判断等式左边之和 sum 是否为0，是的话表示找到解了，返回 true，否则返回 false。若 cur 不等于变量总个数，则继续解析当前字母，还是尝试 [0, 9] 区间内的所有数字，当前已经用过的数字不能在用了，根据 used 数组来判断，还有若当前字母是某个单词的首字母，则不能为0，通过 nonLeadingZero 数组来判断。若当前值可用的话，则在 used 数组中标记为 true，然后调用递归函数，此时传入 cur+1，sum 变为 sum + charCnt[charList[cur]] * i，因为多解析了一个字母，所以要加上该解析值乘以其系数的值。若返回值为 true，则说明找着了，直接返回 true 即可。否则将该 used 中的该解析值充值为 false，for 循环退出后返回 false 即可，参见代码如下（注意这里所有的数组都没有用 C++ STL 中的 vector，而是用的C语言中的指针数组，不然会超时）：

class Solution {
public:
    bool isSolvable(vector<string>& words, string result) {
        unordered_set<char> charSet;
        int charCnt[91] = {};
        bool nonLeadingZero[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 题目讲解汇总(持续更新中...)