lc306-Additive Number

發表於   |   分類於   |   0 comments   |   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution(object):
    def isAdditiveNumber(self, num):
        """
        :type num: str
        :rtype: bool
        """
        l = len(num);
        if l < 3:
            return False
        for i in range(1, l - 1):
            first = int(num[:i])
            for j in range(i + 1, l):
                if num[i] == "0" and i + 1 != j:
                    continue
                second = int(num[i:j])
                for k in range(j + 1, l + 1):
                    if num[j] == "0" and j + 1 != k:
                        continue
                    third = int(num[j:k])
                    if first + second == third:
                        if k == l or self.isAdditiveNumber(num[i:]):
                            return True
            if num[0] == "0" and i == 1:
                break
        return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution(object):
    def isAdditiveNumber(self, num):
        """
        :type num: str
        :rtype: bool
        """
        return self.my(0, 0, 0, 0, num)
    def my(self, first, second, first_len, second_len, num):
        l = len(num);
        if l < 3:
            return False
        if first == 0 and second == 0:
            for i in range(1, l - 1):
                first = int(num[:i])
                first_len = i
                for j in range(i + 1, l):
                    if num[i] == "0" and i + 1 != j:
                        continue
                    second = int(num[i:j])
                    second_len = j - i
                    for k in range(j + 1, l + 1):
                        if num[j] == "0" and j + 1 != k:
                            continue
                        third = int(num[j:k])
                        third_len = k - j
                        if third_len < first_len or third_len < second_len:
                            continue
                        if first + second == third:
                            #print first, second, third
                            if k != l and l - k + 1 < third_len:
                                continue
                            if k == l or self.my(second, third, second_len, third_len, num[first_len:]):# == second + third or second + third == int(num[k:]) or self.my(num[j:]) == third:
                                return True
                if num[0] == "0" and i == 1:
                    break
            return False
        else:
            third_expected = first + second
            third_expected_str = str(third_expected)
            third_expected_len = len(third_expected_str)
            #third = num[sl + tl:third_expected_len + sl + tl]
            return num[first_len+second_len:].startswith(third_expected_str) and \
                    (third_expected_len + first_len + second_len == l or \
                    self.my(second, third_expected, second_len, third_expected_len, num[first_len:]))