在Python中解決CryptArithmetic問題時陷入無限回圈

我正在使用回溯解決 LeetCode，

class Solution:
    def isSolvable(self,words, result):
        characterMap={}
        uniqueString=""

        for word in words:
            for letter in word:
                if letter not in characterMap:
                    uniqueString =letter
                    characterMap[letter]=-1
        
        for r in result:
            if r not in characterMap:
                uniqueString =r
                characterMap[r]=-1
        
                
        self.words=words
        self.result=result
        self.uniqueString=uniqueString
        self.characterMap=characterMap
        self.usedDigit={i:False for i in range(10)}

        
        return self.isSolvableHelper(0)
    
    def getSum(self, word):
        sums=""
        for w in word:
            sums =str(self.characterMap[w])
        
        return int(sums)
    
    def isSolvableHelper(self, idx):
        if(idx==len(self.uniqueString)):
            sumUp=0
            for w in self.words:
                sumUp =self.getSum(w)
            
            resultSum=self.getSum(self.result)
            
            return True if(resultSum==sumUp) else False
        
        char=self.uniqueString[idx]
        for i in range(10):
            if(not self.usedDigit[i]):
                self.characterMap[char]=i
                self.usedDigit[i]=True
                self.isSolvableHelper(idx 1)
                self.usedDigit[i]=False
                self.characterMap[char]=-1

sol=Solution()
sol.isSolvable(['SEND','MORE'], "MONEY")

我已經考慮了與輸入相同的示例，其中單詞 array/list =["SEND", "MORE"]并且結果是MONEY

我遇到了一個無限回圈，不確定這是在哪里發生的，我懷疑它可能是回溯開始的塊 這是輸出，它只是繼續運行

你能幫我知道我的邏輯有什么錯誤嗎？

uj5u.com熱心網友回復：

當您找到解決方案時，您永遠不會回傳 True ：在 isSolvableHelper 中：

            for i in range(10):
                if(not self.usedDigit[i]):
                    self.characterMap[char]=i
                    self.usedDigit[i]=True
                    # in the next line you do not test the returned value, so you do not know when you have finished
                    self.isSolvableHelper(idx 1)
                    self.usedDigit[i]=False
                    self.characterMap[char]=-1

添加測驗：

            for i in range(10):
                if(not self.usedDigit[i]):
                    self.characterMap[char]=i
                    self.usedDigit[i]=True
                    If  self.isSolvableHelper(idx 1):
                        return True
                    self.usedDigit[i]=False
                    self.characterMap[char]=-1
            # Do not forget to return False 
            return False

您還可以僅使用整數來優化 getSum ：

    def getSum(self, word):
        #print("getSum({})".format(word))
        sums=0
        for w in word:
            sums = 10 * sums   self.characterMap[w]
    
        return sums

一些結果：（一個回圈 = isSolvableHelper 中的一個條目）

SEND MORE = MONEY
Char map : {'E': 8, 'D': 7, 'M': 0, 'O': 3, 'N': 1, 'S': 2, 'R': 6, 'Y': 5}
nb loop : 730250

SIX SEVEN SEVEN = TWENTY
Char Mao : {'E': 8, 'I': 5, 'N': 2, 'S': 6, 'T': 1, 'W': 3, 'V': 7, 'Y': 4, 'X': 0}
nb loop : 4094645

THIS IS TOO = FUNNY
Char map : {'F': 0, 'I': 8, 'H': 6, 'O': 5, 'N': 1, 'S': 2, 'U': 4, 'T': 3, 'Y': 9}
nb loop : 2272068

LEET CODE = POINT
no char map
nb loop : 6235301

標籤：Python 递归 回溯

上一篇：跨多行刮一個句子|遞回錯誤未解決

下一篇：在這種情況下如何使用python遞回？