Memoization 기반 Recursive Search로 Factorial 복잡도 해결

Context

두 문자열의 Scramble 가능 여부를 판단하기 위해 모든 경우의 수를 탐색해야 하는 과제 직면. 단순 생성 방식 채택 시 문자열 길이 n에 따라 Factorial Complexity가 발생하는 구조적 한계 존재.

Technical Solution

• Search-based approach를 통한 불필요한 문자열 생성 배제 및 탐색 범위 최적화
• State 변수를 활용한 Custom Memoization 구현으로 중복 계산 제거 및 시간 복잡도 개선
• 문자열을 Head와 Tail로 분할하여 상대 문자열의 Front/Back과 비교하는 Recursive Logic 설계
• 단순 일치 사례를 우선 처리하는 Early Return 전략으로 불필요한 재귀 호출 최소화
• 재귀 깊이에 따른 Log Indentation 적용으로 복잡한 호출 스택의 가시성 확보
• Memoize 모듈 대신 직접 구현한 캐시를 통해 depth 인자로 인한 Cache Miss 방지