I am solving a problem from 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")
I have considered the same example as input where the words array/list = ["SEND", "MORE"]
and the result is MONEY
I run into an inifinite loop not sure where this happens, I suspect that its probably the block where the backtracking begins This is the output, it just goes on running
can you help me to know whats the mistake in my logic here.
CodePudding user response:
You never return True when you find a solution : in 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
Add a test :
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
You can also optimise getSum by using only integers :
def getSum(self, word):
#print("getSum({})".format(word))
sums=0
for w in word:
sums = 10 * sums self.characterMap[w]
return sums
Some results : (one loop = one entry in 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