給定一個(gè)由字母組成的等式，其中每一個(gè)字母表示一個(gè)數(shù)字。不同字母表示的數(shù)字一定不同。問(wèn)字母和數(shù)字之間是否存在一一對(duì)應(yīng)關(guān)系，使得等式成立。若存在多種方案輸出按字母順序排列后字典序最小的解。

比如 SEND+MORE=MONEY 的一個(gè)解為 9567+1085=10652。

解題思路

根據(jù)題意我們可以得到下面幾個(gè)條件：

最多只會(huì)有10個(gè)數(shù)字，所以解的組合數(shù)不超過(guò) 10!=3,628,800最多允許存在10個(gè)字母，否則一定是No Solution當(dāng)單詞長(zhǎng)度超過(guò)1時(shí)，其首字母肯定不為0

一個(gè)簡(jiǎn)單的解法

首先我們需要將所有字母都找出來(lái)，按照字典序排列。再?gòu)牡谝粋€(gè)字母開(kāi)始按字典序枚舉數(shù)字，當(dāng)給每一個(gè)字母分配了數(shù)字之后，將其帶入等式，檢查是否相等。

枚舉數(shù)字時(shí)需要注意有的字母不能等于0，這一步我們可以在預(yù)處理中完成，用數(shù)組notZero表示該字母是否不能為0。

那么可以寫出偽代碼：

dfs(letter):
????startNum?=?0
????If?(notZero[?letter?])?Then?
????????startNum?=?1
????End?If
????For?i?=?startNum?..?9
????????If?not?useNum[i]?Then
????????????useNum[i]?=?true
????????????val[?letter?]?=?i
????????????If?letter?is?last?letter?Then
????????????????If?(check(val))?Then
????????????????????Return?True
????????????????End?If
????????????Else?
????????????????If?(dfs(next?letter))?Then
????????????????????Return?True
????????????????End?If
????????????End?If
????????????val[?letter?]?=?-1
????????????useNum[i]?=?false
????????End?If
????Return?False

val表示每個(gè)字母對(duì)應(yīng)的數(shù)字，初始化為-1useNum表示已經(jīng)使用了的數(shù)字，初始為為falsecheck(val)表示將現(xiàn)在的val帶入原公式檢查是否合法

由于等式長(zhǎng)度最大為100，有可能出現(xiàn)兩個(gè)長(zhǎng)度為49的數(shù)字進(jìn)行比較，顯然無(wú)法正常的采用轉(zhuǎn)化為整數(shù)再進(jìn)行比較的方法。

對(duì)于這樣的情況，我們有如下的解決方案：

首先將等式右邊的單詞全部移到左邊，這樣公式就變成了形如：

word1?+?word2?+?...?+?word4?-?word5?-?word6?-?...?-?word8?=?0

舉個(gè)例子：SEND+MORE-MONEY=0

將其寫成筆算的形式

+??SEND
+??MORE
-?MONEY
-------
??????0

接下來(lái)我們從最低位開(kāi)始，一位一位向高位進(jìn)行計(jì)算。假設(shè)前一位的進(jìn)位為w，則當(dāng)前位的總和為當(dāng)前位所有出現(xiàn)過(guò)的字母之和加上w。最低位時(shí)，因?yàn)榭隙](méi)有進(jìn)位，所以w?= 0。

每一位的和為：s?=?D?+?E?-?Y?+?w。

由于我們之前已經(jīng)枚舉出了所有字母表示的數(shù)字，因此我們可以直接得到這個(gè)和s。

由于我們要使得最后的結(jié)果為0，所以s的末尾一定需要為0。

因此判定合法的條件為s % 10 == 0。

若s滿足末尾為0，則我們可以繼續(xù)向高位計(jì)算，新的進(jìn)位為?w = s / 10。

當(dāng)計(jì)算到最高位時(shí)，不能產(chǎn)生進(jìn)位，還需要額外判斷s = 0。

偽代碼為：

check(val)
????w?=?0
????For?i?=?low?order?..?high?order
????????s?=?sigma(digit?at?order?i)?+?w?//?val
????????If?(s?%?10?!=?0)?Then
????????????Return?False
????????End?If
????????If?(i?==?high?order?&&?s?!=?0)?Then
????????????Return?False
????????End?If
????????w?=?s?/?10
????End?For
????Return?True

假設(shè)一共出現(xiàn)了m個(gè)字母，n種字母。則該算法枚舉組合的時(shí)間復(fù)雜度為?O(10! / (10 - n)!)?~=O(10!)，檢查是否合法的時(shí)間復(fù)雜度為?O(m)，總的時(shí)間復(fù)雜度為 _O(10!*m)_

對(duì)于給定的時(shí)間限制肯定是會(huì)TLE的，因此我們需要對(duì)其進(jìn)行優(yōu)化。

優(yōu)化一

在上面的算法中，我們是按照字母順序以及字典序開(kāi)始搜索?？偸窃诿杜e完全部的字母后，才進(jìn)行匹配。然而實(shí)際上我們會(huì)遇到這樣的情況：

比如DCBA+DCCA-DDDA=0，當(dāng)我們枚舉出A的值時(shí)，已經(jīng)可以判定等式最后一位是否能夠滿足要求。但是在上面的算法中，我們并沒(méi)有這么做，而是一直在枚舉后面的字母。

因此我們提出一個(gè)改進(jìn)的方法，我們按照從低位到高位的過(guò)程中，字母出現(xiàn)的順序去枚舉。這樣做有一個(gè)好處和一個(gè)壞處：

好處是，能夠在最短時(shí)間內(nèi)檢查出是否合法，而不需要去對(duì)整個(gè)等式進(jìn)行檢查。

壞處是，必須要枚舉出所有可能的組合情況，并從中選取字典序最小的情況。

但實(shí)際上，由于該方法剪枝的強(qiáng)度比較大，所以對(duì)于大多數(shù)情況都能夠很好的解決。除了一種特殊的情況，這個(gè)我們會(huì)在優(yōu)化二中講到。

該算法的實(shí)現(xiàn)要點(diǎn)：

根據(jù)筆算公式

+??SEND
+??MORE
-?MONEY

從右到左，從上到下，同時(shí)計(jì)算w和s的值。設(shè)最大的位數(shù)為m位，一共有n個(gè)單詞。我們用(i,j)來(lái)表示當(dāng)前枚舉到了右起第i位，上起第j個(gè)字母。比如在上面例子中(1,1)就是右上角的D，(2,3)就是MONEY中的E。

當(dāng)枚舉到的字母(i,j)尚未賦值時(shí)，枚舉它可能出現(xiàn)的值；否則直接使用已經(jīng)枚舉的值。當(dāng)j = n + 1時(shí)，表示該位所有的字母都已經(jīng)枚舉完畢，此時(shí)計(jì)算w和s并根據(jù)結(jié)果，決定是否遞歸計(jì)算(i+1,1)。當(dāng)i = m + 1時(shí)，表示所有位置都已經(jīng)枚舉完畢，此時(shí)根據(jù)進(jìn)位的w是否等于0，來(lái)判定當(dāng)前解是否合法。

偽代碼實(shí)現(xiàn)為：

dfs(i,?j,?s):
????If?(i?==?m?+?1)?Then
????????If?(s?==?0)?Then
????????????UpdateAns()
????????End?If
????????Return?
????End?If
????If?(j?==?n?+?1)?Then
????????If?(s?%?10?==?0)?Then
????????????dfs(i?+?1,?1,?s?/?10)?//?直接將w加入s
????????Else
????????????Return?
????????End?If
????End?If
????letter?=?getLetter(i,?j)
????If?(val[?letter?]?!=?-1)?Then
????????dfs(i,?j?+?1,?s?+?val[?letter?]?*?op[j])
????Else
????????startNum?=?0
????????If?(notZero[?letter?])?Then?
????????????startNum?=?1
????????End?If
????????For?i?=?startNum?..?9
????????????If?not?useNum[i]?Then
????????????????useNum[i]?=?true
????????????????val[?letter?]?=?i
????????????????dfs(i,?j?+?1,?s?+?val[?letter?]?*?op[j])
????????????????val[?letter?]?=?-1
????????????????useNum[i]?=?false
????????????End?If
????????End?If
????End?If

優(yōu)化二

上面優(yōu)化搜索順序之后的代碼，能夠通過(guò)絕大部分的測(cè)試點(diǎn)，但是仍然有一種情況沒(méi)有辦法做到。當(dāng)碰到下面這種形式時(shí)，就會(huì)超時(shí)：

A+B+C+D+E+F+G+HJJJJJJJJJJJJJJ=A+B+C+D+E+F+G+IJJJJJJJJJJJJJJ

超時(shí)的原因是因?yàn)槠渲?個(gè)字母都在最低位出現(xiàn)了，所以全部進(jìn)行了枚舉。并且只有當(dāng)計(jì)算到最高位時(shí)才能確定這兩個(gè)數(shù)是否相等。

對(duì)于這種數(shù)據(jù)，我們仔細(xì)觀察會(huì)發(fā)現(xiàn)其中ABCDEFGJ的值實(shí)際上無(wú)論等于多少都可以，需要注意的只有H和I的值。

舉一個(gè)簡(jiǎn)單的例子：A+B+C=AB

由于等式左右兩邊都有在個(gè)位的B，所以B的取值并不會(huì)對(duì)計(jì)算個(gè)位的s產(chǎn)生影響。對(duì)于這樣的字母我們稱之為無(wú)用的字母。

對(duì)于上面那個(gè)會(huì)超時(shí)的例子，我們可以發(fā)現(xiàn)，除了H和I以外全部都是無(wú)用的字母。枚舉他們的值完全是沒(méi)有必要的，我們只在一個(gè)字母出現(xiàn)，并且有用時(shí)才去枚舉它的值。

因此我們先做一次預(yù)處理，將所有無(wú)用的字母都標(biāo)記出，在枚舉時(shí)直接跳過(guò)。

當(dāng)然這樣做還有一個(gè)問(wèn)題：某一種字母每一次出現(xiàn)都是無(wú)用的字母，那么當(dāng)我們找到合法答案時(shí)，該字母并沒(méi)有賦值。

此時(shí)我們將剩余的數(shù)字按照最小序依次賦值給它們即可。

因此原偽代碼改為：

dfs(i,?j,?s):
????If?(i?==?m?+?1)?Then
????????If?(s?==?0)?Then
????????????fillAns()???//?賦值剩余的數(shù)字
????????????UpdateAns()
????????End?If
????????Return?
????End?If
????If?(j?==?n?+?1)?Then
????????If?(s?%?10?==?0)?Then
????????????dfs(i?+?1,?1,?s?/?10)?//?直接將w加入s
????????Else
????????????Return?
????????End?If
????End?If
????letter?=?getLetter(i,?j)?//?若該字母為無(wú)用的字母，則返回-1
????If?(letter?==?-1)?Then??//?處理無(wú)用的字母
????????dfs(i,?j?+?1,?s)
????????Return?;
????End
????If?(val[?letter?]?!=?-1)?Then
????????dfs(i,?j?+?1,?s?+?val[?letter?]?*?op[j])
????Else
????????startNum?=?0
????????If?(notZero[?letter?])?Then?
????????????startNum?=?1
????????End?If
????????For?i?=?startNum?..?9
????????????If?not?useNum[i]?Then
????????????????useNum[i]?=?true
????????????????val[?letter?]?=?i
????????????????dfs(i,?j?+?1,?s?+?val[?letter?]?*?op[j])
????????????????val[?letter?]?=?-1
????????????????useNum[i]?=?false
????????????End?If
????????End?If
????End?If

加上第二種優(yōu)化之后，就解決特殊情況，也就能夠順利地通過(guò)所有的測(cè)試點(diǎn)了。