口算难题Java
文章发布较早，内容可能过时，阅读注意甄别。
# 题目
给你一个方程，左边用 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
# 思路
HashSet
# 解法
class Solution {
Set<Character> forbidden = new HashSet<>();//长度大于1的字符串开头字母禁止为0
public boolean isSolvable(String[] words, String result) {
int maxLen = result.length();
for(int i = 0 ; i < words.length ; i++){
maxLen = Math.max(words[i].length(),maxLen);
if(words[i].length() > 1){
forbidden.add(words[i].charAt(0));
}
}
if(maxLen > result.length()){//左边不能存在比result还长的字符串
return false;
}
if(result.length() > 1){
forbidden.add(result.charAt(0));
}
List<String> list = new ArrayList<>();
for(int i = 0 ; i < words.length ; i++){
list.add(getStr(words[i],maxLen));//统一长度，方便计算每一位的和
}
Map<Character,Integer> map = new HashMap<>();
boolean[] isUsed = new boolean[10];
return solve(map,list,result,maxLen-1,0,isUsed,0);
}
public boolean solve(Map<Character,Integer> map, List<String> list, String result, int index, int start, boolean[] isUsed, int add){
if(index == -1){
if(add != 0){
return false;
}
return true;
}
char c;
boolean mark = true;//是否出现过递归
for(int i = start ; i < list.size() ; i++){
c = list.get(i).charAt(index);
if(c == '#'){
continue;
}
if(!map.containsKey(c)){//存在未确认的字符，需要递归确定值
for(int j = 0 ; j < 10 ; j++){
if(!isUsed[j]){
if(j == 0 && forbidden.contains(c)){//剪枝
continue;
}
isUsed[j] = true;
map.put(c,j);
if(solve(map,list,result,index,i+1,isUsed,add)){
return true;
}
map.remove(c);
isUsed[j] = false;
}
}
mark = false;
break;
}
}
if(mark){//说明没有出现过递归，已经具备了所需要的值，可以校验当前位置了
int leftVal = add;//获取左式当前位置上值的总和，同时考虑进位add
for(int i = 0 ; i < list.size() ; i++){
c = list.get(i).charAt(index);
if(c != '#'){
leftVal += map.get(c);
}
}
add = leftVal/10;//新的进位
int m = leftVal % 10;//当前位置的值
c = result.charAt(index);
if(map.containsKey(c)){//检查右式字符的值是否等于m
if(m == map.get(c)){
return solve(map,list,result,index-1,0,isUsed,add);
}else{
return false;
}
}
//右式字符尚未确定，首先保证m没有被多次使用
if(isUsed[m]){
return false;
}
//同样禁止前导0
if(m == 0 && forbidden.contains(c)){
return false;
}
map.put(c,m);
isUsed[m] = true;
if(solve(map,list,result,index-1,0,isUsed,add)){
return true;
}
map.remove(c);
isUsed[m] = false;
return false;
}
return false;
}
public String getStr(String s, int len){
int diff = len-s.length();
if(diff == 0){
return s;
}
String str = "";
for(int i = 0 ; i < diff ; i++){
str += "#";
}
return str+s;
}
}
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
# 总结
- 分析出几种情况，然后分别对各个情况实现
