So I am trying to solve the Leetcode decode ways problem (https://leetcode.com/problems/decode-ways/) and I find their solution confusing.
def recursiveWithMemo(self, index, s) -> int:
# If you reach the end of the string
# Return 1 for success.
if index == len(s):
return 1
# If the string starts with a zero, it can't be decoded
if s[index] == '0':
return 0
if index == len(s)-1:
return 1
answer = self.recursiveWithMemo(index 1, s)
if int(s[index : index 2]) <= 26:
answer = self.recursiveWithMemo(index 2, s)
return answer
def numDecodings(self, s: str) -> int:
return self.recursiveWithMemo(0, s)
I am not able to understand, why the index == len(s) and index == len(s) - 1 conditions are used? Is index == len(s) - 1 not sufficient to check whether we have reached end of string?
CodePudding user response:
index == len(s) - 1
is sufficient to check wether we have reached the end of the string, but still in this algorithm they are taking steps of size 2
. Checking id index == len(s)
is not becuase they want to check if they are reached the end of string or not, but rather they are checking this to not to encounter an error in the next line :
# If the string starts with a zero, it can't be decoded
if s[index] == '0':
return 0
if index = len(s)
condition if s[index] == 0
would give you an error.