COP 3337
  Section U05
  Spring 2017



                     The Bobadilla Strings
                     =====================



   We define the Bobadilla strings as follows:

   1. "ab" and "ca" are Bobadilla.

   2. If S is a Bobadilla string, then S + S + "cb" is Bobadilla.

   3. If S and T are Bobadilla strings, then S + "ac" + T is Bobadilla.
      Here S and T can be equal or not.

   For example,

   4. "ab" is Bobadilla by rule 1.

   5. We take S = "ab", apply rule 2 and we get the Bobadilla string "ababcb".

   6. "ca" is a Bobadilla string by rule 1.

   7. We take S = "ab" and  T = "ca", apply rule 3 and get the Bobadilla string
        "abacca".

   8. We take S=T = "abacca", apply rule 3 and get the Bobadilla string
      "abaccaacabacca".

     Write the method

     public static boolean isBobadilla(String in)

     that returns true if the string in is Bobadilla and false if it is not.
     Write your answer below.

     Answer:
     -------
   
    // check if in is a Bobadilla string
    public static boolean isBobadilla(String in)
    {
        if (in == null)
            return false;
        if (in.equals("ab") || in.equals("ca"))
            return true; // base cases
        int len = in.length();

        // all other strings of length < 6  and all strings of odd length
        // are not Bobadilla
        if (len < 6 || len % 2 == 1)
            return false;

        // check rule 2
        int mid = len / 2  - 1 ;
        String s1 = in.substring(0, mid);
        String s2 = in.substring(mid, len-2);
        String last = in.substring(len-2);
        if (last.equals("cb") && s1.equals(s2) && isBobadilla(s1))
            return true;

        // check rule 3
        for (int i = 2; i < len - 2; i = i + 2)
        {
            // check if in at i is a
            if (in.substring(i,i+2).equals("ac"))
            {
                String s = in.substring(0,i);
                String t = in.substring(i+2);
                if (isBobadilla(s) && isBobadilla(t))
                    return true;
            }
        }

        // in is not Bobadilla
        return false;

    }