두 개의 문자열 s와 t와 두 개의 값 p와 q가 있다고 가정합니다. 우리는 s가 ≤ p를 가질 마지막 그룹을 제외하고 p개의 문자 그룹으로 분리되고 각 그룹에서 최대 q개의 문자를 선택할 수 있도록 s에서 t를 얻을 수 있는지 확인해야 합니다. 또한 t의 문자 순서는 s와 같아야 합니다.
따라서 입력이 s ="mnonnopeqrst", t ="moprst", p =5, q =2와 같으면 출력은 "mnonn", "opeqr", "st"와 같이 나눌 수 있으므로 True가 됩니다. , 이제 "mnonn" 및 "opeqr"에서 2개의 문자 부분 문자열 "mo" 및 "pr"을 가져오면 "st"가 이미 있으므로 이 두 길이 부분 문자열을 사용하여 간단한 연결로 t를 생성할 수 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- temp :=모든 키에 대한 빈 목록을 포함하는 빈 맵
- l :=길이가 s이고 0으로 채워지는 크기의 목록
- 0에서 s 크기의 범위에 있는 i에 대해 다음을 수행합니다.
- temp['a'] 끝에 i 삽입
- 낮음 :=0
- 0에서 t - 1 사이의 범위에 있는 i에 대해 다음을 수행합니다.
- 인덱스 :=temp['a']
- it :=정렬된 순서를 유지하기 위해 인덱스 목록에 낮은 값을 삽입하는 인덱스
- 인덱스의 크기 - 1과 같으면
- 거짓을 반환
- count :=(index[it] / p)의 몫
- l[count] :=l[count] + 1
- l[count]>=q이면
- 카운트 :=카운트 + 1
- 낮음 :=개수 * p
- 그렇지 않으면
- 낮음 :=인덱스[it] + 1
- 참 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
from bisect import bisect_left from collections import defaultdict def solve(s, t, b, m) : temp = defaultdict(list) l = [0] * len(s) for i in range(len(s)) : temp['a'].append(i) low = 0 for i in range(len(t)) : indices = temp['a'] it = bisect_left(indices, low) if it == len(indices) : return False count = indices[it] // b l[count] = l[count] + 1 if l[count] >= m : count += 1 low = count * b else : low = indices[it] + 1 return True s = "mnonnopeqrst" t = "moprst" p = 5 q = 2 print (solve(s, t, p, q))
입력
"mnonnopeqrst", "moprst", 5, 2
출력
True