algorithm - 解析表示为字符串的数字并返回满足斐波那契关系的数字数组

Question

给定一个字符串形式的数字，返回满足 arr[i] = arr[i-1] + arr[i-2] 的数字数组。

Example:-
'112358' = [1,1,2,3,5,8]
'1111213' = [11,1,12,13]
'1111223' = [1,11,12,23]

Answer 1

解决方案的伪代码是:

input: string with size n
output: string_array[m]

for i <- 2 to n 
     create all possible non-empty two splitting and 
     generate the sequence based on those two.
         if somewhere the generated sequence does not match with the input "string"
              try another splitting. 
         else:
              return the found splitting with all generated numbers.

将一个大小为k的字符串拆分成两个字符串的可能次数是k-1。此外，生成序列并检查字符串的最后部分是 O(n)。因此这个算法的时间复杂度是sum_{k = 2}^n (k-1)n = n sum_{k = 2}^n (k-1) = O(n^3).