길이가 같은 두 개의 비어 있지 않은 문자열 s와 t가 있다고 가정합니다. s와 t 부분 문자열의 각 쌍이 같은 크기이고 서로의 아나그램이 되도록 부분 문자열로 분할해야 합니다. 이제 s와 t의 최대 절단 수가 되도록 절단 인덱스를 찾으십시오. 결과가 없으면 빈 목록을 반환합니다.
따라서 입력이 s ="bowcattiger" t ="owbactietgr"과 같으면 출력은 [0, 3, 5, 6, 10]이 됩니다. 각 문자열이 다음과 같이 되도록 문자열을 5개의 파티션으로 분할할 수 있기 때문입니다. 서로의 아나그램. s =["활", "ca", "t", "tige", "r"], t =["owb", "ac", "t", "ietg", "r"]
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 간격:=새 목록
- cs :=s에 있는 문자와 빈도가 있는 지도
- ct :=t에 존재하는 문자와 그 빈도가 있는 지도
- cs가 ct와 같지 않으면
- 새 목록 반환
- x 범위 크기가 s - 1에서 0까지인 경우 다음을 수행합니다.
- cs[s[x]] :=cs[s[x]] - 1
- ct[t[x]] :=ct[t[x]] - 1
- cs가 ct와 같으면
- 간격 끝에 x 삽입
- 목록 간격을 정렬하고 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
from collections import Counter class Solution: def solve(self, a, b): intervals = [] ca = Counter(a) cb = Counter(b) if ca != cb: return [] for x in reversed(range(len(a))): ca[a[x]] -= 1 cb[b[x]] -= 1 if ca == cb: intervals.append(x) return sorted(intervals) ob = Solution() s = "bowcattiger" t = "owbactietgr" print(ob.solve(s, t))
입력
"bowcattiger", "owbactietgr"
출력
[0, 3, 5, 6, 10]