크기가 같은 두 개의 문자열 s와 t가 있다고 가정합니다. s와 t가 같은지 여부를 확인해야 합니다. 확인해야 할 몇 가지 조건이 있습니다.
- 둘 다 평등합니다. 또는,
- s를 동일한 크기의 인접한 두 개의 하위 문자열로 나누고 하위 문자열이 s1과 s2이고 t도 마찬가지로 s를 t1과 t2로 나누면 다음 중 하나가 유효해야 합니다.
- s1은 t1과 재귀적으로 동일하고 s2는 t2와 재귀적으로 동일합니다.
- s1은 t2와 재귀적으로 동일하고 s2는 t1과 재귀적으로 동일합니다.
따라서 입력이 s ="ppqp" t ="pqpp"인 경우 출력은 s와 t를 s1 ="pp", s2 ="qp" 및 t1 ="pq의 두 부분으로 나누는 것처럼 True입니다. ", t2 ="pp", 여기 s1 =t2이고 s2와 t1을 두 부분으로 나누면 s21 ="q", s22 ="p", t11 ="p", t12 ="q", 여기에서도 s21 =t12 및 s22 =t11이므로 재귀적으로 동일합니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- util() 함수를 정의합니다. 시간이 걸립니다
- s의 크기가 홀수이면
- 반환
- left :=util(s의 왼쪽 절반)
- right :=util(s의 오른쪽 절반)
- (왼쪽 연결 오른쪽), (오른쪽 연결 왼쪽)의 최소값 반환
- 기본 메소드에서 util(s)이 util(t)와 같으면 true를 반환하고 그렇지 않으면 false를 반환합니다.
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시 코드
def util(s): if len(s) & 1 != 0: return s left = util(s[0:int(len(s) / 2)]) right = util(s[int(len(s) / 2):len(s)]) return min(left + right, right + left) def solve(s,t): return util(s) == util(t) s = "ppqp" t = "pqpp" print(solve(s, t))
입력
"ppqp", "pqpp"
출력
True