I posted my solutions last night. @steve.j.sun pointed out checking
num == '0' at the very beginning would make "011235" invalid, which actually is valid. Then, I realized actually
num == '0' should still be checked at the beginning of the outer loop for being leading 0 so that "0235813" would be claimed as invalid.
It seems like leetcode is missing these two test cases for now, though the expected answers would be right for both cases.
The problem is "Given a string represents an integer, write a function to determine if it's an additive number." And there is no clue in the description that an input string could not start with '0'. Especially, the Leetcode solution does expect "011235" valid.
So, I guess there are two options for Leetcode:
a) modifying the description to say input string starting with '0' is invalid and updating its solution for getting expected answers.
b) adding test cases like "011235" and "0235813" into its pool.
Thanks stpeterh! The reason why I removed the test cases that have leading zeros(in the input string) is that I want to eliminate any inconsistency.
If the problem doesn't allow any number in the additive sequence to have leading zeros but the input number does (int the test case), some people might think that's unfair :)
If the solution passes existing test cases, it's supposed to work for test cases like "011235" as long as the idea of the algorithm is correct.
Please correct me if I am wrong, thanks mate!
Thanks for your explanation, @jeantimex. This is not necessarily true: "If the solution passes existing test cases, it's supposed to work for test cases like "011235" as long as the idea of the algorithm is correct."
My original solution passed all the test cases, but did not work for test cases like "011235". The reason is I check whether the input string starts with '0' at the very begining:
class Solution(object): def isAdditiveNumber(self, num): """ :type num: str :rtype: bool """ if num is None or len(num) < 3 or num == '0': return False n = len(num) for i in range(1, n): for j in range(i+1, n): first, second, third = 0, i, j if num[second] == '0' and third > second + 1: break while third < n: result = str(int(num[first:second]) + int(num[second:third])) if num[third:].startswith(result): first, second, third = second, third, third + len(result) else: break if third == n: return True return False
Thanks @stpeterh, you mentioned that "num == '0' should still be checked at the beginning of the outer loop for being leading 0 so that "0235813" would be claimed as invalid.", but the problem description only says "numbers in the additive sequence cannot have leading zeros", it doesn't say whether leading zeros in the input string is valid or not (that's why I have removed those test cases to avoid confusion), I am not sure why you have to make that sanity check.
Thanks @jeantimex. I was trying to make my solution consistent with the OJ solution. It seems like the OJ solution assumes that leading zeros in the input string is valid, at least for cases like "011235".
I agree with you, the key point of this problem is to determine first two elements. Of course the first number could be '0'.
First, additive number is an integer, not a string. So the problem should be interpreted as "Given a string represents an integer, write a function to determine if this integer is an additive number."
Strictly speaking based on this interpretation, "011235" should be considered as valid, because it represents the integer 11235. And therefore, the valid sequence should be "1, 1, 2, 3, 5", not "0, 1, 1, 2, 3, 5". And "0235813" should also be considered as valid, because it represents 235813, which is an additive number.
Anyway, this is how the problem should be strictly interpreted, but I don't think this is the intention when the problem was created. I would like to see if we can add more restriction or clarification to the problem.
Thanks, @WHJ425. I agree with your interpretation and analysis about the problem. Indeed, it is a problem about problem description, which is not the main intention of this problem.
Sorry for the late response, guys. I have added both test cases as suggested by @stpeterh and modified the description a little. I think it should be clear that the string input may start with '0', please let me know otherwise. Thanks.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.