길이가 같은 두 개의 문자열과 b가 있다고 가정합니다. 인덱스를 선택하고 선택한 인덱스에서 두 문자열을 모두 분할해야 합니다. 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가 회문을 형성하는지 확인하십시오. (모든 분할은 빈 문자열일 수 있음)
따라서 입력이 ="pqrst" b ="turqp"와 같으면 ["pq", "rst"]와 b를 ["tu", "rqp"와 같이 나눌 수 있기 때문에 출력은 True가 됩니다. ], 그래서 만약 우리가 b_suff와 함께 _pref를 조인한다면, 회문인 "pqrqp"를 얻게 될 것입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
쌍 목록에서 각 쌍 (x, y)에 대해 [(a, b), (b, a)], do
-
i :=0, j :=x의 크기 - 1
-
x[i]는 y[j]와 같고 i
0, do -
나는 :=나는 + 1
-
j :=j - 1
-
-
midx :=인덱스 i에서 j까지 x의 부분 문자열
-
midy :=인덱스 i에서 j까지 y의 부분 문자열
-
midx가 회문이거나 midy가 회문이면
-
참을 반환
-
-
-
거짓을 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
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