• 문자열 길이가 최대 1000이기 때문에 bfs로 진행하면 :2^{1000}: 이 된다.
  • A와 B가 마지막에 동일하게 붙는다는 사실과 함께 거꾸로 가면 길이 하나라는 걸 깨달았다.
  • 맨 뒤가 B이면 제거 및 문자열을 reverse하고, 맨 뒤가 A이면 제거만 한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26



import java.io.*;
import java.util.*;

public class Main {
	static String src, dest;

	static int solution() {
		StringBuilder sb = new StringBuilder(dest);
		while (sb.length() > src.length()) {
			if (sb.charAt(sb.length()-1) == 'B') {
				sb.setLength(sb.length()-1);
				sb.reverse();
			} else
				sb.setLength(sb.length()-1);
		}
		return sb.toString().equals(src)? 1 : 0;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		src = in.readLine();
		dest = in.readLine();

		System.out.println(solution());
	}
}