240603 A와 B 2

private static String start;

public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	start = br.readLine();
	String target = br.readLine();
	System.out.println(canTransform(target) ? 1 : 0);
}

private static StringBuilder sb = new StringBuilder();

private static boolean canTransform(String current) {
	if (current.length() == start.length()) {
		return current.equals(start);
	}

	sb.setLength(0);
	sb.append(current);
	if (sb.charAt(sb.length() - 1) == 'A') {
		sb.deleteCharAt(sb.length() - 1);
		if (canTransform(sb.toString())) {
			return true;
		}
	}

	sb.setLength(0);
	sb.append(current).reverse();
	if (sb.charAt(sb.length() - 1) == 'B') {
		sb.deleteCharAt(sb.length() - 1);

		if (canTransform(sb.toString())) {
			return true;
		}
	}

	return false;
}

출처:https://www.acmicpc.net/problem/12919