두 개의 문자열 s와 t가 있다고 가정하고 k 이동 이하로 s가 t로 변환될 수 있는지 확인해야 합니다. i번째 이동에서는 이러한 작업을 수행할 수 있습니다.
-
이전 이동에서 1 <=j <=크기 s 및 j가 선택되지 않도록 s에서 인덱스 j(1부터 시작)를 선택하고 해당 인덱스 i의 문자를 여러 번 이동합니다.
-
그대로 두십시오.
여기서 문자를 이동한다는 것은 알파벳의 다음 문자로 대체하는 것을 의미합니다(문자가 'z'인 경우 'a'로 줄바꿈). 따라서 문자를 i번 이동하는 것은 이동 작업을 i번 적용한다는 것을 나타냅니다.
따라서 입력이 s ="poput" t ="vwput" k =9와 같으면 출력은 True가 됩니다. 왜냐하면 i =6에서 'p'를 'v'로 변환할 수 있고 i =8에서 'o'를 'w'로 변환할 수 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다.
-
s의 크기가 t의 크기와 같지 않으면
-
거짓을 반환
-
-
count :=0에서 25까지의 모든 i에 대해 (최소 1 및 (k - i + 1 +(k - i)/26))를 보유하는 배열
-
s의 각 문자 c1과 t의 c2에 대해 수행
-
c1이 c2와 같지 않으면
-
diff :=(c2의 ASCII - c1의 ASCII + 26) mod 26
-
count[diff] <=0이면
-
거짓을 반환
-
-
개수[차이] :=개수[차이] - 1
-
-
-
참을 반환
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
예시
def solve(s, t, k): if len(s) != len(t): return False count = [min(1, k - i + 1) + (k - i)//26 for i in range(26)] for c1, c2 in zip(s, t): if (c1 != c2): diff = (ord(c2) - ord(c1) + 26) % 26 if count[diff] <= 0: return False count[diff] -= 1 return True s = "poput" t = "vwput" k = 9 print(solve(s, t,k))
입력
"poput","vwput",9
출력
True