Bruteforce/BackTracking Algorithm to Split Array into Fibonacci

  • 时间:2020-09-07 13:13:13
  • 分类:网络文摘
  • 阅读:85 次

Given a string S of digits, such as S = “123456579”, we can split it into a Fibonacci-like sequence [123, 456, 579]. Formally, a Fibonacci-like sequence is a list F of non-negative integers such that:

0 <= F[i] <= 2^31 – 1, (that is, each integer fits a 32-bit signed integer type);
F.length >= 3;
and F[i] + F[i+1] = F[i+2] for all 0 <= i < F.length – 2.

Also, note that when splitting the string into pieces, each piece must not have extra leading zeroes, except if the piece is the number 0 itself.

Return any Fibonacci-like sequence split from S, or return [] if it cannot be done.

Example 1:
Input: “123456579”
Output: [123,456,579]

Example 2:
Input: “11235813”
Output: [1,1,2,3,5,8,13]

Example 3:
Input: “112358130”
Output: []
Explanation: The task is impossible.

Example 4:
Input: “0123”
Output: []
Explanation: Leading zeroes are not allowed, so “01”, “2”, “3” is not valid.

Example 5:
Input: “1101111”
Output: [110, 1, 111]
Explanation: The output [11, 0, 11, 11] would also be accepted.

Note:
1 <= S.length <= 200
S contains only digits.

Bruteforce and Back Tracking Algorithm to Split String into Fibonacci Numbers

The start of the Fiboancci Numbers can be obtained via Bruteforce algorithms in O(N^2). Once we determine the first two numbers, we can start backtracking searching in the rest of of the string.

We also need to make sure the numbers in the sequence are smaller than the 32-bit signed integer (231-1). Once the search reaches the end and matches the current Fiboancci number, we can simply return the array.

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
class Solution {
public:
    vector<int> splitIntoFibonacci(string S) {
        for (int i = 0; i < S.size(); ++ i) {            
            string aa = S.substr(0, i + 1);
            if (tooBig(aa)) break;
            int a = atoi(aa.c_str());    
            if (a < 0) continue;
            for (int j = i + 1; j + aa.size() < S.size(); ++ j) {                
                vector<int> r;       
                r.push_back(a);
                string bb = S.substr(i + 1, j - i);          
                if (tooBig(bb)) break;
                if ((bb[0] == '0') && (bb.size() > 1)) break;
                int b = atoi(bb.c_str());
                r.push_back(b);
                if (check(S.substr(j + 1), a, b, r)) {
                    return r;
                }
            }
        }
        return {};
    }
    
private:
    bool tooBig(string x) {
        const string BIG = "2147483647";
        return (x.size() > BIG.size()) || ((x.size() == BIG.size()) && (x > BIG));
    }
    
    bool check(string num, int64_t prev, int64_t cur, vector<int> &r) {
        int64_t next = prev + cur;
        string x = std::to_string(next);
        if (tooBig(x)) return false;
        if (num.size() < x.size()) return false;
        if (num.substr(0, x.size()) != x) return false;
        r.push_back(next);
        if (num.size() == x.size()) {            
            return true;
        }
        return check(num.substr(x.size()), cur, next, r);
    }
};
class Solution {
public:
    vector<int> splitIntoFibonacci(string S) {
        for (int i = 0; i < S.size(); ++ i) {            
            string aa = S.substr(0, i + 1);
            if (tooBig(aa)) break;
            int a = atoi(aa.c_str());    
            if (a < 0) continue;
            for (int j = i + 1; j + aa.size() < S.size(); ++ j) {                
                vector<int> r;       
                r.push_back(a);
                string bb = S.substr(i + 1, j - i);          
                if (tooBig(bb)) break;
                if ((bb[0] == '0') && (bb.size() > 1)) break;
                int b = atoi(bb.c_str());
                r.push_back(b);
                if (check(S.substr(j + 1), a, b, r)) {
                    return r;
                }
            }
        }
        return {};
    }
    
private:
    bool tooBig(string x) {
        const string BIG = "2147483647";
        return (x.size() > BIG.size()) || ((x.size() == BIG.size()) && (x > BIG));
    }
    
    bool check(string num, int64_t prev, int64_t cur, vector<int> &r) {
        int64_t next = prev + cur;
        string x = std::to_string(next);
        if (tooBig(x)) return false;
        if (num.size() < x.size()) return false;
        if (num.substr(0, x.size()) != x) return false;
        r.push_back(next);
        if (num.size() == x.size()) {            
            return true;
        }
        return check(num.substr(x.size()), cur, next, r);
    }
};

When we do the back tracking, we can discard current search branch if the current number in the Fiboancci does not appear at the begin of the string. Instead of String.startsWith or IndexOf checks, we can use substring to get the same length of the begining of the string and compare the equality. If the string is itself the current number of Fibonacci number, we have found a good path – then we need to return true.

Also, we need to make sure the numbers does not start with ‘0’ except the number ‘0’ itself. The runtime complexity is O(N^3).

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
Marketing Tips for E-Commerce Websites  5 Tips for Staying Safe Online  10 Signs Your Blog is Working  The Key to Risk-Free Cloud-Based IT Equipment Shipping  Bring Your Multi-Site Development Work To The Next Level With A   
How to Create Killer SEO Content on a Budget  Learn to Achieve Your Goals with 5 Secrets of Great Bloggers  What is Cornerstone Content And Why It’s Important  How to Attract Female Readership For Your Blog  Double your traffic with White Hat SEO techniques 
评论列表
添加评论