口算难题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

# 总结

分析出几种情况，然后分别对各个情况实现

#Java