目录

1. 问题描述

2. 解题思路

3. 代码及测试

4. 优化

1. 问题描述

        所谓字母算式，就是用字母表示的算式，规则是相同字母对应相同数字，不同字母对应不同数字，并且第一位字母的对应数字不能是 0。

        譬如给定算式 We * love = CodeIQ，则可以对应填上下面这些数字以使之成立。

        W = 7, e = 4, l = 3, o = 8, v = 0, C = 2, d = 1, I = 9, Q = 6

        这样一来，我们就能得到 74 * 3804 = 281496 这样的等式。使这个字母算式成立的解法只有这一种。

        求使下面这个字母算式成立的解法有多少种？

        READ + WRITE + TALK = SKILL

2. 解题思路

        本题解着眼于通用的解决方案，即不仅限于以上表达式，而是任意的字符串表达式（前提式的确能够代表合法的算法，比如说运算符不能连续出现，等等）。

基本步骤如下：

        Step1: 从输入字符串中提取出表示数字（即除运算符和等号外）（不重复, or unique）字符集合

        Step2: 遍历以上所有字符与数字(0~9)的映射方式，假定有k个字符，则有P(10,k)中排列，每一种排列对应一种映射方式

            Step2-1将每一种映射方式代入到输入字符串得到字符串算式

            Step2-2 判断所得到的字符串算式是否是合法的

            Step2-3 分别评估字符串算式的LHS（Left-hand-side:左手边表达式）和RHS（Right-hand-side:右手边表达式）并判断是否相等

        在Step2中用python itertools模块中的permutation()生成所有的组合。

        在Step2-3中用pyhton内置的eval()函数进行字符串形式的算式值的评估

        在 Step2-2中判断字符串表达式是否合法依据的规则是多位数字的操作数的第一个字母不能为0。首先基于‘=’的位置分割得到LHS和RHS。

        RHS中因为没有运算符所以比较简单，只要有多位数字（长度大于1）且首位为0就表示是非法表达式。

        LHS的情况比较复杂，分以下三种情况考虑：

1. 第一个操作数的判断：如果LHS[0]为0且LHS[1]仍为数字则表明肯定非法
2. 其后，搜索每个运算符，如果运算符后的第一个字符为0且第二个字符仍为数字，则为非法
3. LHS的最后一个字符不能为操作符—这个判断，基于以下假设其实并不需要

        当然以上判断方法是基于原输入字符串表达式肯定可以表达成一个合法的算式，比如不会有两个连续的运算符出现，等等。

3. 代码及测试

# -*- coding: utf-8 -*-"""Created on Sun Sep  5 08:39:27 2021@author: chenxy"""import sysimport timeimport datetimeimport math# import randomfrom   typing import List# from   queue import Queue# from   collections import dequeimport itertools as itclass Solution:    def stringEquation(self, strEqu:str):        """        strEqu: Equation in the form of string with character representing digit,                 assuming case insensitive.                Also it is assumed that only integer division is considered        :ret: The total number of IP satisfying the requirement        """                        # Step1: extract the alphabeta characters from the string equation            s = strEqu.upper() # Transfer to all uppercase for the convenience of processing                cLst = []        for k in range(len(s)):                        if s[k].isalpha() and s[k] not in cLst:                cLst.append(s[k])            if s[k] == "=":                equalSignIndex = k        # print(cLst)                        nums = 0        mapping = []        for p in it.permutations([k for k in range(10)], len(cLst)):             # print(p)            # Substitute c<->digit mapping back to the input string equation            # left-hand-side expression, before "="                        lhs = s[0:equalSignIndex]            for k in range(len(cLst)):                lhs = lhs.replace(cLst[k], str(p[k]))                            # right-hand-side expression, after "="            rhs = s[equalSignIndex+1:]            for k in range(len(cLst)):                rhs = rhs.replace(cLst[k], str(p[k]))                                        # print(lhs, rhs)            if len(rhs) > 1 and rhs[0] == "0" : # The first digit must be non-zero in multi-digit case                # print("1")                continue            if len(lhs) > 1 and lhs[0] == "0" and lhs[1].isdigit():                # print("2")                continue            if not lhs[-1].isdigit():                # print("3", lhs, lhs[-1].isdigit() )                continue                                    lhs_valid = True            for k in range(len(lhs)-2):                if (not lhs[k].isdigit()) and lhs[k+1]=="0" and lhs[k+2].isdigit():                    # print("invalid lhs:", lhs)                    lhs_valid = False                    break            if not lhs_valid:                continue                        # print("valid:", lhs, rhs, eval(lhs), eval(rhs))            if eval(lhs) == eval(rhs):                nums = nums + 1                mapping.append((cLst,p,lhs+"="+rhs))                return nums, mapping

if __name__ == "__main__":                        sln    = Solution()                tStart = time.time()    strEqu = "A*B=C"    nums, mapping = sln.stringEquation(strEqu)    tCost  = time.time() - tStart    print("nums={0}, tCost = {1:6.3f}(sec)".format(nums,tCost))       for item in mapping:        print("/t",item)        tStart = time.time()    strEqu = "We*love=CodeIQ"    nums, mapping = sln.stringEquation(strEqu)    tCost  = time.time() - tStart    print("nums={0}, tCost = {1:6.3f}(sec)".format(nums,tCost))        for item in mapping:        print("/t",item)        tStart = time.time()    strEqu = "READ+WRITE+TALK=SKILL"    nums, mapping = sln.stringEquation(strEqu)    tCost  = time.time() - tStart    print("nums={0}, tCost = {1:6.3f}(sec)".format(nums,tCost))            for item in mapping:        print("/t",item)    

nums=10, tCost = 46.159(sec)
     (["R", "E", "A", "D", "W", "I", "T", "L", "K", "S"], (1, 6, 3, 2, 4, 9, 7, 8, 0, 5), "1632+41976+7380=50988")
     (["R", "E", "A", "D", "W", "I", "T", "L", "K", "S"], (2, 5, 4, 3, 7, 0, 6, 9, 1, 8), "2543+72065+6491=81099")
     (["R", "E", "A", "D", "W", "I", "T", "L", "K", "S"], (4, 9, 0, 5, 2, 6, 8, 1, 7, 3), "4905+24689+8017=37611")
     (["R", "E", "A", "D", "W", "I", "T", "L", "K", "S"], (5, 0, 9, 4, 7, 3, 1, 6, 2, 8), "5094+75310+1962=82366")
     (["R", "E", "A", "D", "W", "I", "T", "L", "K", "S"], (5, 0, 9, 6, 3, 7, 1, 8, 2, 4), "5096+35710+1982=42788")
     (["R", "E", "A", "D", "W", "I", "T", "L", "K", "S"], (5, 1, 8, 0, 6, 9, 2, 4, 3, 7), "5180+65921+2843=73944")
     (["R", "E", "A", "D", "W", "I", "T", "L", "K", "S"], (5, 2, 7, 0, 8, 1, 3, 6, 4, 9), "5270+85132+3764=94166")
     (["R", "E", "A", "D", "W", "I", "T", "L", "K", "S"], (7, 0, 9, 2, 3, 5, 1, 8, 6, 4), "7092+37510+1986=46588")
     (["R", "E", "A", "D", "W", "I", "T", "L", "K", "S"], (7, 0, 9, 2, 4, 3, 1, 8, 6, 5), "7092+47310+1986=56388")
     (["R", "E", "A", "D", "W", "I", "T", "L", "K", "S"], (9, 7, 2, 8, 1, 4, 6, 0, 5, 3), "9728+19467+6205=35400")

4. 优化

        以上虽然得出的正确的结果，但是运行速度有点衰，需要考虑进一步的优化。

        上一篇：Q12: 平方根数字

        下一篇：Q14: 国名接龙

        本系列总目录参见：程序员的算法趣题：详细分析和Python全解