目錄

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全解