소문자 문자열 s가 있다고 가정합니다. 이제 s의 모든 문자를 삭제, 삽입 또는 업데이트할 수 있는 작업을 고려하십시오. 모든 문자열 t에 대해 s =(t 연결 t)를 만드는 데 필요한 최소 작업 수를 계산해야 합니다.
따라서 입력이 s ="pqrxqsr"과 같으면 출력은 2가 됩니다. "x"를 "p"로 업데이트하고 "s"를 삭제할 수 있기 때문에 s는 "pqrpqr"이고 이것은 s =t는 t ="pqr"에 대해 t를 연결합니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- edit_distance() 함수를 정의합니다. s1, s2가 걸립니다.
- m :=s1의 크기
- n :=s2의 크기
- cur :=범위 0에서 n까지의 새 목록
- 0 ~ m - 1 범위의 i에 대해
- 이전 :=cur
- cur :=(i + 1) 다음에 n개의 0이 있는 목록
- 0 ~ n - 1 범위의 j에 대해 다음을 수행합니다.
- cur[j + 1] :=s1[i]와 s2[j]가 같으면 prev[j] (최소 cur[j], prev[j], prev[j + 1]) + 1
- 리턴 커[n]
- 메인 방법에서 다음을 수행하십시오. -
- res :=s의 크기
- 0 ~ s - 1 크기 범위의 i에 대해
- res :=edit_distance(인덱스 0에서 i - 1까지 s의 부분 문자열, 인덱스 i에서 끝까지 s의 부분 문자열) 및 res 의 최소값
- 반환 결과
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(s): def edit_distance(s1, s2): m, n = len(s1), len(s2) cur = list(range(n + 1)) for i in range(m): prev, cur = cur, [i + 1] + [0] * n for j in range(n): cur[j + 1] = (prev[j] if s1[i] == s2[j] else min(cur[j], prev[j], prev[j + 1]) + 1) return cur[n] res = len(s) for i in range(len(s)): res = min(edit_distance(s[:i], s[i:]), res) return res s = "pqrxqsr" print(solve(s))
입력
"pqrxqsr"
출력
None