[python] 백준 12919 A와 B 2

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

12919번: A와 B 2

 

문제 해결

• 처음에 S->T로 만드는 BFS 함수를 생각했다.
• 하지만 메모리초과, 시간초과 나오는 것을 보고 다른방법을 생각하게 되었다.
• 이전에 긴 문자열에서 짧은 문자열을 만드는 풀이가 생각이 났다.
• 역시 문자열을 만드는 것은 긴 문자열에서 짧은 문자열로 생각하는 것이 정답이다.(그래야 비교할 경우의 수가 줄어든다.)

 

CODE

S = str(input())
T = str(input())
def solve(word):
    if word == S:
        print(1)
        exit()
    if len(word) <= len(S):
        return
    if word[0] == 'B':
        word_1 = word[::-1]
        word_1 = word_1[:-1]
        solve(word_1)
    if word[-1] == 'A':
        word_2 = word[:-1]
        solve(word_2)

solve(T)
print(0)