FibonacciString

public class FibonacciString {
    /**
     * 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.
     *
     * @param str
     * @return
     */
    public static boolean isFibonacciString(String str) {
        // To be a fib string, the string must have at least three elements.
        // Start searching for the two start elements by taking the first two
        // characters of the string.
        return str.length() >= 3
                && getSetups(Integer.parseInt(str.charAt(0) + ""),
                        Integer.parseInt(str.charAt(1) + ""), str.substring(2));
    }

    static boolean getSetups(int n2, int n1, String str) {
        // if n2 is greater than or equal to n1 and there are no more elements
        // to try, this is not a fib string
        if (str.length() < 1 && n2 >= n1) {
            return false;
        }
        // check if the current set up is a fib string. Otherwise, check whether
        // appending the next element in string to n1 will work. Otherwise,
        // check whether incrementing n2 and resetting n1 will work
        return (str.length() > 0 && n1 >= n2 && isSetupFib(n2, n1, str))
                || (str.length() > 0 && getSetups(n2,
                        Integer.parseInt(n1 + "" + str.charAt(0)),
                        str.substring(1)))
                || (str.length() < 1 && getSetups(
                        Integer.parseInt("" + n2 + ("" + n1).charAt(0)),
                        Integer.parseInt(("" + n1).substring(1, 2)),
                        ("" + n1).substring(2)));
    }

    static boolean isSetupFib(int n2, int n1, String str) {
        // the sequence has ended perfectly, there are no straggling numbers
        if (str.length() < 1) {
            return true;
        }
        int n = n2 + n1;
        String nStr = n + "";
        // check if the next term in the string is what it should be, elem(n-2)
        // + elem(n-1). If it is not, the string is automatically not a fib
        // string.
        if (str.length() < nStr.length()
                || !str.substring(0, nStr.length()).equals(nStr)) {
            return false;
        }
        // if so far the elements are correct, check the next term
        return isSetupFib(n1, n, str.substring(nStr.length()));
    }
}