두 개의 문자열 s와 t가 있다고 가정하면 s가 s의 하위 문자열을 만드는 데 필요한 최소 연산량을 찾아야 합니다. 이제 각 작업에서 s의 임의의 위치를 선택하고 해당 위치의 문자를 다른 문자로 변경할 수 있습니다.
따라서 입력이 s ="abbpqr", t ="bbxy"와 같으면 하위 문자열 "bbpq"를 가져와서 'p'를 'x'로, 'q'를 '로 변경할 수 있으므로 출력은 2가 됩니다. 요'.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- k :=t의 크기, n :=s의 크기
- ans :=10^10
- 0 ~ n - k 범위의 i에 대해
- ss :=s의 부분 문자열[인덱스 i에서 i+k-1까지]
- ans :=s 및 t의 일치하지 않는 문자 수 및 최소 ans
- 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class Solution:
def solve(self, s, t):
k, n = len(t), len(s)
ans = 10**10
for i in range(n - k + 1):
ss = s[i:i+k]
ans = min(ans, sum(ss[j]!=t[j] for j in range(k)))
return ans
ob = Solution()
print(ob.solve("abbpqr", "bbxy")) 입력
"abbpqr", "bbxy"
출력
2