TopCoder Practice - ABBA

abba_answer.java

public class Main {
  public String canObtain(String initial, String target) {
    // Target is always longer than initial
    if (canObtainHelper(initial, target)) {
      return "Possible";
    } else {
      return "Impossible";
    }
  }
  
  public boolean canObtainHelper(String curr, String target) {
    // Base Cases
    if (curr.equals(target)) {
      return true;
    }
    if (curr.length() >= target.length()) {
      return false;
    }
    // Stopping conditions
    if (!(isSubstring(curr, target) || isReverseSubstring(curr, target))) {
      return false;
    }
    return canObtainHelper(curr+"A", target) || canObtainHelper(reverse(curr)+"B", target);
  }

  public boolean isSubstring(String curr, String target) {
    return target.contains(curr);
  }

  public boolean isReverseSubstring(String curr, String target) {
      String reversedTarget = reverse(target);
      return isSubstring(curr, reversedTarget);
  }

  public String reverse(String word) {
    StringBuffer b = new StringBuffer();
    for (int i = word.length() - 1; i >= 0; i--) {
      b.append(word.charAt(i));
    }
    return b.toString();
  }

  public static void main(String[] args) {
    Main m = new Main();
    String result = m.canObtain("BBBBABABBBBBBA", "BBBBABABBABBBBBBABABBBBBBBBABAABBBAA");
    System.out.println(result);
  }
}

notes.md

My solution passed all the tests but I found a nicer solution

The better solution works by saying that if the last letter is A, then we can only obtain target if we can obtain target(0, n-1). If the last letter is B then we can only obtain target if we can obtain reverse(target(0, n-1)).

question.txt

One day, Jamie noticed that many English words only use the letters A and B. Examples of such words include "AB" (short for abdominal), "BAA" (the noise a sheep makes), "AA" (a type of lava), and "ABBA" (a Swedish pop sensation).

Inspired by this observation, Jamie created a simple game. You are given two s: initial and target. The goal of the game is to find a sequence of valid moves that will change initial into target. There are two types of valid moves:

Add the letter A to the end of the string.
Reverse the string and then add the letter B to the end of the string.
Return "Possible" (quotes for clarity) if there is a sequence of valid moves that will change initial into target. Otherwise, return "Impossible".