Python에서 두 문자열 사이의 편집 거리가 1인지 확인하십시오.

두 개의 문자열 s와 t가 있다고 가정합니다. s와 t 사이의 편집 거리가 정확히 1인지 확인해야 합니다. 여기서 두 문자열 사이의 편집은 다음 세 가지 중 하나를 의미합니다 -

• 문자 삽입
• 캐릭터 삭제
• 문자 바꾸기

따라서 입력이 s ="hello" t ="heillo"와 같으면 t를 얻기 위해 s에 한 문자를 삽입해야 하므로 출력은 True가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• s의 크기 - t의 크기|> 1, 다음
  • 거짓 반환
• edit_dist_cnt :=0, i :=0, j :=0
• i
• s[i]가 t[j]와 같지 않으면
  • edit_dist_cnt가 1과 같으면
    • 거짓 반환
  • s의 크기> t의 크기인 경우
    • 나는 :=나는 + 1
  • 그렇지 않으면 s의 크기
  • j :=j + 1
• 그렇지 않으면
  • i :=i + 1, j :=j + 1
• edit_dist_cnt :=edit_dist_cnt + 1

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

def solve(s, t):
   if abs(len(s) - len(t)) > 1:
      return false
   edit_dist_cnt = 0
   i = 0
   j = 0
   while i < len(s) and j < len(t):
      if s[i] != t[j]:
         if edit_dist_cnt == 1:
            return false
         if len(s) > len(t):
            i += 1
         elif len(s) < len(t):
            j += 1
         else:
            i += 1
            j += 1
         edit_dist_cnt +=1
      else:
         i += 1
         j += 1
   if i < len(s) or j < len(t):
      edit_dist_cnt += 1
   return edit_dist_cnt == 1
s = "hello"
t = "heillo"
print(solve(s, t))

입력

"hello", "heillo"

출력

True