问题描述

想问朋友面试中遇到的一个算法题：

Write a program in Java to assess a given string whether it complies with following patterns. Return true if a given string complies with these patterns else false.

N = N1 + N2
N>= N1 >= N2

where N is the Nth element in the string or element at Nth position;
N1 is the (N-1) element in the string & N2 is the (N-2) element in the string.

Example 1: 224610
Elements in this string are 2, 2, 4, 6, 10.
First Set: 2+2=4 (N2=2; N1=2 & N= 4);
Second Set: 2+4=6 (N2=2; N1=4 & N=6);
Third Set: 4+6=10 (N2=4; N1=6 & N= 10)

Example 2: 1112233558
Elements in this string are 1, 11, 12, 23, 35, 58

Example 3: 1101102203
Elements in this string are 1, 101, 102, 203.
怎么样确定数字的位数呢？

解决方案

这就是费波拉契数列，不需要判断位数，只要尝试就可以了。
而且因为N>=N1>=N2，所以第二个数的位数也必然>=第一个，所以尝试的运算量进一步降低。

解决方案二：

而且我们知道99+999=1098，因此N的位数最多也就比N2的位数大1，最小不会小于N2的位数，我们可以这么尝试：
假设整个字符串长度是L，让N=(L-1)/2
1 1 1
1 1 2
1 2 2
1 2 3
...
1 N N
2 2 2
2 2 3
...