길이가 서로 같은 두 문자열 a와 b가 있다고 가정해 보겠습니다. 임의의 인덱스를 하나 선택해 두 문자열을 모두 해당 위치에서 분할합니다. 이때 문자열 a는 a_pref와 a_suff로 나뉘어 a = a_pref | a_suff를 만족하고(|는 연결 연산자), 문자열 b 역시 b_pref와 b_suff로 나뉘어 b = b_pref + b_suff가 됩니다. 우리가 확인해야 할 것은 a_pref + b_suff 또는 b_pref + a_suff가 회문(palindrome)을 이루는지 여부입니다. 단, 분할 지점은 자유롭게 정할 수 있으며 분할 결과로 빈 문자열이 나오는 것도 허용됩니다.
예를 들어 입력이 a = "pqrst", b = "turqp"라고 해보겠습니다. 이 경우 출력은 True입니다. a를 ["pq", "rst"]로, b를 ["tu", "rqp"]로 분할한 뒤 a_pref와 b_suff를 이어 붙이면 "pqrqp"라는 회문을 얻을 수 있기 때문입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다 −
[(a, b), (b, a)] 쌍 목록에서 각각의 쌍(x, y)에 대해 아래 과정을 수행합니다.
i := 0, j := x의 길이 − 1 로 초기화합니다.
x[i]가 y[j]와 같고, i < x의 길이이며, j > 0인 동안 반복합니다.
i := i + 1
j := j − 1
midx := x의 인덱스 i부터 j까지의 부분 문자열
midy := y의 인덱스 i부터 j까지의 부분 문자열
midx가 회문이거나 midy가 회문이라면,
True를 반환합니다.
모든 쌍을 검사한 후에도 회문을 찾지 못했다면 False를 반환합니다.
핵심 아이디어는 다음과 같습니다. 양 끝에서부터 두 포인터를 안쪽으로 이동시키며 서로 일치하는 문자들을 최대한 매칭합니다. 그러면 가운데 남은 구간만 회문인지 확인하면 되는데, 이때 남은 두 부분 문자열(midx, midy) 중 어느 하나라도 회문이라면 전체 문자열이 회문이 될 수 있습니다. (a, b)와 (b, a) 두 방향을 모두 검사하는 이유는 앞부분과 뒷부분을 교차 조합하는 두 가지 경우를 모두 커버하기 위함입니다. 시간 복잡도는 O(n)으로 효율적입니다.
예제
다음 구현 예시를 통해 더 자세히 이해해 보겠습니다 −
def solve(a, b):
for x, y in [[a, b], [b, a]]:
i, j = 0, len(x) - 1
while x[i] == y[j] and i<len(x) and j>0:
i += 1
j -= 1
midx = x[i:j+1]
midy = y[i:j+1]
if (midx == midx[::-1] or midy== midy[::-1]):
return True
return False
a = "pqrst"
b = "turqp"
print(solve(a, b))
입력
"pqrst", "turqp"
출력
True