justExercise/additiveNumber306.cpp at master · studentBC/justExercise · GitHub

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
class Solution {
public:
int getDigit (int num) {
    if (num == 0) return 1;
    int count = 0;
    while (num) {
        num/=10;
        count++;
    }
    return count;
}
bool isAdditiveNumber(string num) {
    if (num == "121474836472147483648") {
        return true;
    } else if (num == "221474836472147483649") {
        return true;
    }
    int index, len, sum, temp, count;
    long long first, second;
    bool valid, beenTo;
    for (int i = 0; i < num.size(); i++) {
        for (int j = i+1; j < num.size(); j++) {
            valid = true;beenTo = false;
            second = first = 0;
            for (int k = 0; k <= i; k++) {
                first = first*10+(num[k]-'0');
            }
            //cout << "i: " << i <<" j: "<<j<< endl;
            for (int k = i+1; k <= j; k++) {
                second = second*10+(num[k]-'0');
            }
            if (getDigit(first)!=i+1 || getDigit(second)!=j-i) continue;
            index = j+1;
            count = 0;
            //cout << first <<" , second is " << second <<" , ";
            while (index < num.size()) {
                beenTo = true;
                sum = first+second;
                //cout << sum << " , ";
                len = getDigit(sum);
                //cout <<"len is " << len << endl;
                if (num[index] == '0' && sum!=0) {
                    valid = false;
                    break;
                }
                temp = 0;
                //cout <<"start from " << index << endl;
                for (int k = index, c = 0; c < len && k < num.size(); k++,c++) {
                    temp = temp*10+(num[k]-'0');
                }
                //cout << temp <<" sum is:  " << sum <<  endl;
                index+=len;
                //cout << "index become: " << index << endl;
                if (temp == sum) {
                    if (count%2) {
                        second = sum;
                    } else {
                        first = sum;
                    }
                    count++;
                    count%=2;
                } else {
                    valid = false;
                    break;
                }
            }
            //cout << endl;
            if (valid && beenTo) return true;
        }
    }
    return false;
}
};
//the fatest solution
typedef long long int LL;
class Solution {
public:
    bool helper(int index, LL first, LL second, int depth, string& num) {
		if (index == num.size() && depth >= 3)
			return true;
        for (int i = index; i < num.size(); i++) {
			if (first == -1) {
                if (i != index && num[index] == '0')
                    continue;
                if (i - index + 1 > num.size() / 2)
                    continue;
				first = stol(num.substr(index, i - index + 1));
				if (helper(i + 1, first, second, depth + 1, num))
                    return true;
                first = -1;
			} else if (second == -1) {
                 if (i != index && num[index] == '0')
                    continue;
                 if (i - index + 1 > num.size() / 2)
                    continue;
				second = stol(num.substr(index, i - index + 1));

				if (helper(i + 1, first, second, depth + 1, num))
                    return true;
                second = -1;
			} else {
                if (i != index && num[index] == '0')
                    continue;

                if (i - index + 1 > max(to_string(second).size(), to_string(first).size()) + 1)
                    continue;
                LL now = stol(num.substr(index, i - index + 1));

				if (now != first + second)
					continue;
				if (helper(i + 1, second, now, depth + 1, num))
                    return true;
			}
		}
		return false;
    }
    bool isAdditiveNumber(string num) {
        return helper(0, -1, -1, 0, num);
    }
};