迭代回溯法, 用两个指针来切割字符串,将字符串分为三个部分,前两部分作为第一个数字和第二个数字,计算他们的和,作为result, 然后在第三部分查找是否以result开头,用startswith()函数判断。如果不是就剪掉,也就是break,如果是,second 变成新的first, third中result部分变成新的second, 剩下变成third,循环下去,判断一下最后third是不是到字符串末尾了,如果到了,return true
class Solution(object):
def isAdditiveNumber(self, num):
"""
:type num: str
:rtype: bool
"""
n = len(num)
if num == None or len(num) < 3:
return False
for i in range(1, n/2+1):
if i > 1 and num[0] == '0':
break
for j in range(i+1, (i+n)/2 + 1):
if j > i+1 and num[i] == '0':
break
first, second, third = 0, i, j
while third < n:
first_num = int(num[first:second])
second_num = int(num[second:third])
result = first_num + second_num
if num[third:].startswith(str(result)):
first, second, third = second, third, third + len(str(result))
else:
break
if third == n:
return True
return False
另一种写法,combinations(iterable,r);创建一个迭代器,返回iterable中所有长度为r的子序列,返回的子序列中的项按输入iterable中的顺序排序
class Solution(object):
def isAdditiveNumber(self, num):
"""
:type num: str
:rtype: bool
"""
n = len(num)
for i, j in itertools.combinations(range(1, n), 2):
print i, j
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
网友评论