1307：口算难题（2250 分）

Ian

2019-12-29 约 709 字预计阅读 2 分钟次阅读

力扣第 169 场周赛第 4 题

题目

给你一个方程，左边用 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

分析

#1

回溯即可，可以从低到高试填

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution:
    def isSolvable(self, words: List[str], result: str) -> bool:
        def dfs(i,c):
            if i==len(result):
                return c==0
            todo = sorted({w[i] for w in words+[result] if i<len(w) and w[i] not in d})
            cands = set(range(10))-set(d.values())
            for sub in permutations(cands,len(todo)):
                d.update(dict(zip(todo,sub)))
                if all(i!=len(w)-1 or len(w)==1 or d[w[i]]!=0 for w in words+[result]):
                    s = sum(d[w[i]] for w in words if i<len(w))
                    c2,s = divmod(s+c,10)
                    if s==d[result[i]] and dfs(i+1,c2):
                        return True
                [d.pop(c) for c in todo]
            return False

        if any(len(w)>len(result) for w in words):
            return False
        words = [w[::-1] for w in words]
        result = result[::-1]
        d = {}
        return dfs(0,0)

1199 ms

#2

还可以从高到低考虑，思路详见力扣官解

权值合并后，先试填权重绝对值高的字母
对待定项，按权重正负分别赋值 9 和 0，即可估算出上下界

解答

 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


class Solution:
    def isSolvable(self, words: List[str], result: str) -> bool:
        d = defaultdict(int)
        for w in words:
            if len(w)>len(result):
                return False
            for i,c in enumerate(w[::-1]):
                d[c] += 10**i
        for i,c in enumerate(result[::-1]):
            d[c] -= 10**i
        bd = defaultdict(int)
        for w in words+[result]:
            if len(w)>1:
                bd[w[0]] = 1
        A = sorted(d.items(),key=lambda p:abs(p[1]))
        n = len(A)
        ma,mi = [0]*n,[0]*n
        for i,(c,w) in enumerate(A):
            ma[i] = ma[i-1]+w*(9 if w>0 else bd[c])
            mi[i] = mi[i-1]+w*(9 if w<0 else bd[c])
        vis = [0]*10
        
        def dfs(i,s):
            if i<0:
                return s==0
            if s+mi[i]<=0<=s+ma[i]:
                c,w = A[i]
                for j in range(bd[c],10):
                    if not vis[j]:
                        vis[j] = 1
                        if dfs(i-1,s+w*j):
                            return True
                        vis[j] = 0
            return False
        return dfs(len(A)-1,0)

5 ms

目录

1307：口算难题（2250 分）

题目

分析

#1

#2

解答