Just trying all possibilities for the first two numbers and checking whether the rest fits.
def isAdditiveNumber(self, num): n = len(num) for i, j in itertools.combinations(range(1, n), 2): a, b = num[:i], num[i:j] if b != str(int(b)): continue while j < n: c = str(int(a) + int(b)) if not num.startswith(c, j): break j += len(c) a, b = b, c if j == n: return True return False
@在线疯狂 Why? That's invalid.
I'm not sure, but I think "0011" for input is valid, Because it is not explicitly mentioned in the problem description. ref: https://leetcode.com/discuss/70230/two-missing-test-cases-in-additive-number
Not all strings are valid. Do you also think "four plus two" is valid input, representing 6? Your "0011" is probably supposed to represent 11, whose normal string representation is "11". Not "0011" or "eleven" or "one more than ten" or whatever one could imagine.
How about this: The problem is called "Additive Number". Not "Additive String". And the definition is "a positive integer whose...". I'd say we get the number as a string for technical reasons (C++ & Co not having arbitrarily large integers) but it's really about the number. And is for example the number 11 additive or not? If you represent it as "11", then it's not, but if you represent it as "011", then it is? How can the same number both be additive and not be additive? Nonsense. No, it's about the number, and the digital representation is "11" and nothing else.
How would you handle the overflow problem?
I wonder if a interviewer will skip this question for a pythoner.
@zhuyinghua1203 I don't really want to think about that :-P. But I guess I'd add a+b one digit at a time and compare it to the rest of the string while doing so. Not sure how to handle that a+b might be longer than both. Maybe instead I'd go from the back, trying all possibilities for the last two numbers and subtracting to get the next number(s) before them...
@zhuyinghua1203 Yeah, I'd definitely go backwards instead of forwards, I think that's a lot simpler. If I go forwards, I only know where the third number starts. But if I go backwards, I know where the third-last number ends. Which is a lot more helpful, because adding/subtracting digit by digit is simpler from right to left.
I think in python we can compare a+b with 2**31-1, but that sounds redundant since python doesn't have overflow problem...
In language like c, if overflow, a+b < 0. And the problem becomes how to do big-number addition in c with string input/output (there may be a separate leetcode problem for this.)
Oh, I misunderstood you. I thought you were already talking about "big numbers". I didn't even realize the minor a+b overflow :-). Yeah, I agree in Python it doesn't make any sense to handle the a+b overflow as Python does that anyway. It could make sense to use our own digit-by-digit addition or subtraction, though, if the numbers can get very big. It might be more efficient because one test can stop after just one digit, whereas turning substrings into ints and then working with those... already spends much time on turning the entire substrings into ints.
@kidd9_ I do check
b for leading zeros, and
a doesn't need to be checked because then the input would have leading zeros and that would be invalid, see the previous comments. Or at least it used to be invalid. I see the problem text has been changed in the meantime (in my opinion it's worse now and I don't intend to adapt my solution).
Clear code! But I have to say that use of itertools.combinations is not efficient. For example, i can not be greater than 2 when a string of 5 characters is given but the combinations (3,4) is still generated and tested.
I modified the fifth line to be
if a != str(int(a)) or b != str(int(b)):
to pass the test case
'0235813' which should be false.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.