소문자의 대상 문자열을 만들고 싶다고 가정합니다. 처음에는 n '?' 표시(n은 대상 문자열의 길이). 소문자 우표도 있습니다. 각 턴에서 시퀀스 위에 스탬프를 배치하고 스탬프의 모든 문자를 해당 스탬프의 해당 문자로 바꿀 수 있습니다. 최대 10 * n 회전을 할 수 있습니다.
예를 들어 초기 시퀀스가 "?????"이고 스탬프가 "abc"라고 생각하면 첫 번째 시퀀스에서 "abc??", "?abc?", "??abc"와 같은 문자열을 만들 수 있습니다. 회전하다. 시퀀스에 스탬프가 찍힐 수 있는 경우 각 턴에서 가장 왼쪽 문자가 스탬프 처리된 인덱스 배열을 반환합니다. 이것이 불가능하면 빈 배열을 반환합니다. 따라서 시퀀스가 "ababc"이고 스탬프가 "abc"이면 답은 [0, 2]와 같을 수 있습니다. -> "ABC??" -> "ababc".
따라서 입력이 s ="abcd" t ="abcdbcd"와 같으면 출력은 [3,0]
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
s의 크기가 1과 같으면
-
t의 모든 문자가 동일하고 s[0]이면 0에서 t까지의 목록을 반환하고, 그렇지 않으면 새 빈 목록을 반환합니다.
-
-
ans :=새 목록
-
반면 t는 "?"의 수 t의 크기와 동일하지 않습니다. 표시, 수행
-
tmp :=t
-
범위 0에서 s까지의 i에 대해
-
j의 경우 s 크기에서 i+1까지:
-
검색 :="?"의 i 번호 s의 하위 문자열 연결[인덱스 i에서 j-1까지] 연결(s - j의 크기) "?"의 수
-
검색이 t에 있는 동안 수행
-
ans 끝의 t에서 검색이 있는 위치에 삽입
-
t :=검색을 "?" 수만큼의 크기로 바꿉니다. 한 번만
-
-
t가 "?"의 수 t의 크기와 같으면
-
루프에서 나오다
-
-
t가 "?"의 수 t의 크기와 같으면
-
루프에서 나오다
-
-
-
tmp가 t와 같으면
-
루프에서 나오다
-
-
-
-
ans의 역순을 반환합니다.
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
def solve(s, t): if len(s) == 1: return [i for i in range(len(t))] if all(t==s[0] for t in t)else [] ans = [] while t != "?" * len(t): tmp = t for i in range(len(s)): for j in reversed(range(i+1, len(s)+1)): search = "?" * i + s[i:j] + "?" * (len(s)-j) while t.find(search) != -1: ans.append(t.find(search)) t = t.replace(search, "?"*len(s), 1) if t == "?" * len(t): break if t == "?" * len(t): break if tmp == t: return [] return ans[::-1] s = "abcd" t = "abcdbcd" print(solve(s, t))
입력
"abcd", "abcdbcd"
출력
[3,0]