문자열 매칭 수 계산

하나 빼기: 문자열을 편집하는 방법에는 세 가지 종류가 있다. 문자 삽입, 문제 삭제, 문자 교체. 문자열 두 개가 주어졌을 때, 문자열을 같게 만들기 위한 편집횟수가 1회 이내인지 확인하는 함수를 작성하라

예시

• pale, ple → true
• pales, pale → true
• pale, bale → true
• pale, bake → false

문자열 매칭 수 >= 긴 문자열의 length - 1
이면 true를 반환하게 처리

import difflib

def get_matching_character_count(str1, str2):
    matcher = difflib.SequenceMatcher(None, str1, str2)
    matching_blocks = matcher.get_matching_blocks()
    matching_characters_count = sum(block.size for block in matching_blocks)
    return matching_characters_count

def is_one_edit_away(str1, str2):
    max_length = max(len(str1), len(str2))
    matching_character_count = get_matching_character_count(str1, str2)

    return matching_characters >= max_length - 1

# 예시 테스트
print(is_one_edit_away("pale", "ple"))   # True
print(is_one_edit_away("pales", "pale")) # True
print(is_one_edit_away("pale", "bale"))  # True
print(is_one_edit_away("pale", "bake"))  # False

물론 difflib을 사용하지 않는 것이 의도된 것이였겠지만
나는 풀이 자체가 중요하므로 패스
필요하다면 문자열 매칭 수 계산을 직접 구현하면 되겠다.

LCS 알고리즘에 대해 찾아보면 되겠다.

function LCSLength(X[1..m], Y[1..n])
    C = array(0..m, 0..n)
    for i := 0..m
        C[i,0] = 0
    for j := 0..n
        C[0,j] = 0
    for i := 1..m
        for j := 1..n
            if X[i] = Y[j]
                C[i,j] := C[i-1,j-1] + 1
            else
                C[i,j] := max(C[i,j-1], C[i-1,j])
    return C[m,n]

출처 : 위키