题目大意：
口算难题
给你一个方程，左边用 words 表示，右边用 result 表示。
你需要根据以下规则检查方程是否可解：
- 每个字符都会被解码成一位数字（0 – 9）。
- 每对不同的字符必须映射到不同的数字。
- 每个 words[i] 和 result 都会被解码成一个没有前导零的数字。
- 左侧数字之和（words）等于右侧数字（result）。
如果方程可解，返回 True，否则返回 False。
示例 1：
输入：words = ["SEND","MORE"], result = "MONEY" 输出：true 解释：映射 'S'-> 9, 'E'->5, 'N'->6, 'D'->7, 'M'->1, 'O'->0, 'R'->8, 'Y'->'2' 所以 "SEND" + "MORE" = "MONEY" , 9567 + 1085 = 10652
示例 2：
输入：words = ["SIX","SEVEN","SEVEN"], result = "TWENTY" 输出：true 解释：映射 'S'-> 6, 'I'->5, 'X'->0, 'E'->8, 'V'->7, 'N'->2, 'T'->1, 'W'->'3', 'Y'->4 所以 "SIX" + "SEVEN" + "SEVEN" = "TWENTY" , 650 + 68782 + 68782 = 138214
示例 3：
输入：words = ["THIS","IS","TOO"], result = "FUNNY" 输出：true
示例 4：
输入：words = ["LEET","CODE"], result = "POINT" 输出：false
提示：
- 2 <= words.length <= 5
- 1 <= words[i].length, results.length <= 7
- words[i], result 只含有大写英文字母
- 表达式中使用的不同字符数最大为 10
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1307
解题思路分析：
本题是一道Hard级别的难题，看完题目之后，第一个想法就是暴力解，因为最多只有10种字符，我们分别用0-9表示每种字符，查看是否存在一种左侧数字之和等于右侧数字的方案即可。解题步骤大致如下：
- 先遍历题目给出的words数组以及result字符串，查看它们都含有哪些大写字母。我们使用一个长度为26的一位boolean型数组来记录出现过的字母，数组下标0-25分别对应字母a-z。如果存在该字母，数组对应下标的值更新为true。
- 使用递归方法为每一个字母赋值，赋值范围是0-9中的一个数字，递归函数的参数需要另一个boolean型数组来记录使用过的数字。递归的顺序为字母a到字母z。递归时，首先查看当前字母是否在words数组以及result字符串中出现过，如果没出现过，那么不需要赋值，直接递归到下一层子方法，查看下一个字母。反之如果出现过，那么我们则需要给当前字母赋值，我们循环0-9，使用每一个还没有使用过的数字来给当前字母赋值，赋值后，将当前数字标记为已经使用过，然后递归到下一层子问题为下一个字母赋值。这里需要注意一点，题目要求每个字符串的首字符不能以0开头，因此，如果当前字母是某个字符串的首字符时，不能赋值为0。
- 递归的结束条件为，当递归到字母z，并且赋值完成之后，说明所有字母都赋值成功，此时，将等式左边的每个单词以及等式右边的结果字符串，按照赋值的数值转化成数字，即可判断其是否相等。
实现代码：
boolean[] has=new boolean[26]; // 记录包含哪些字符
boolean[] firstChar = new boolean[26]; // 记录哪些字符是字符串的首字符
public boolean isSolvable(String[] words, String result) {
// 遍历每个单词
for(String w : words){
// 查看单词包含哪些字符
for(int i=0;i<w.length();i++){
int index=w.charAt(i)-'A';
has[index]=true;
if(i==0) firstChar[index]=true;
}
}
// 遍历result字符串每个字符，查看包含哪些字符
for(int i=0;i<result.length();i++){
int index=result.charAt(i)-'A';
has[index]=true;
if(i==0) firstChar[index]=true;
}
// 记录字符对应的数字（下标0-25代表字符A-Z）
int[] num = new int[26];
// 默认为-1
Arrays.fill(num, -1);
// 递归赋值
return dfs(words, result, num, 0, new boolean[10]);
}
// words为题目给出的等式左边所有字符串
// result为题目给出的等式右边字符串
// num为字符对应的数字
// letter为当前字符
// numUsed为使用过的数字
// 返回值为是否能够使等式相等
boolean dfs(String[] words, String result, int[] num, int letter, boolean[] numUsed){
if(letter==26){ // 26个字母都赋值完成时
int r=0; // 计算result对应的数字
for(int i=0;i<result.length();i++){
r= r*10+num[result.charAt(i)-'A'];
}
int sum=0; // 计算等式左边所有字符串对应数字之和
for(String w : words){
int n=0;
for(int i=0;i<w.length();i++){
n= n*10+num[w.charAt(i)-'A'];
}
sum+=n;
}
// 返回等式两边是否相等
return sum==r;
}
// 如果当前字母是题目给出的字符
if(has[letter]){
// 尝试从0-9循环赋值
for(int j=0;j<10;j++){
// 如果当前数字已经被使用过，跳过
if(numUsed[j]) continue;
// 如果当前数字是0，并当前字符是某个字符串的首字符，跳过
if(j==0&&firstChar[letter]) continue;
// 将当前字母赋值为当前数字
num[letter]=j;
// 记录当前数字已经使用过
numUsed[j]=true;
// 递归到下一个字母
if(dfs(words,result,num,letter+1,numUsed)) return true;
num[letter]=-1;
numUsed[j]=false;
}
}else{
// 如果当前字母不是题目给出的字符
// 递归到下一个字母
return dfs(words,result,num,letter+1,numUsed);
}
return false;
} 本题解法执行时间为1337ms。
Runtime: 1371 ms, faster than 24.04% of Java online submissions for Verbal Arithmetic Puzzle.
Memory Usage: 34.7 MB, less than 100.00% of Java online submissions for Verbal Arithmetic Puzzle.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1307-verbal-arithmetic-puzzle-解题思路分析/