Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
TopCoder Practice - ABBA
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);
}
}

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)).

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".
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.