1.5 하나빼기

문제

문자열을 편집하는 방법에는 세가지가 있다. 문자 삽입, 문자 삭제, 문자 교체.

문자열 두개가 주어졌을때 문자열을 같게 만들기 위한 편집횟수가 1회 이내인지 확인하는 함수를 만들어라.

 

예제

pale,ple ->true

pales,pale ->true

pale,bale ->true

pale,bake ->false

 

접근법

1. 모든 문자열 편집 가능 수를 구해서 비교한다 -> 절대안돼 time Complexity 너무 커져

 

2. 문자 삽입, 삭제, 교체의 특징을 확인하여 구현

- 문자 삽입과 삭제는 두 문자열의 길이차이가 1을 넘지 않아야하며, 긴문자열에서 짧은 문자열과 다른 부분을 발견했을때 한번의 인덱스 이동만 허용하고 나머지 글자는 동일한지 확인해보아야한다.

- 문자 교체는 두 문자열의 길이가 같고 글자가 한번만 다르고 나머지가 동일한지 체크해야한다.

def replace (s1, s2):
    is_changed = False
    
    for i in range(len(s1)):
        if s1[i] != s2[j] :
            if is_changed : return False
            is_changed = True
    return True

def insert(s1, s2):
    is_changed = False
    j = 0
    for i in range(len(s1)):
        if s1[i] != s2[j]:
            if is_changed : return False
            is_changed = True
        else :
            j +=1
    return True

def Solution(s1, s2):
    len_diff = len(s1)-len(s2)
    if len_diff == 0 :
        return replace(s1, s2)
    elif len_diff == -1 :
        return insert(s2, s1)
    elif len_diff ==1  :
        return insert(s1, s2)
    else :
        return False

3. 삽입, 삭제, 교체를 분리하지 않고 구현 ( 비슷한 코드가 많으니까! ) 

def Solution(s1, s2):
    len_diff = len(s1)-len(s2)
    if len_diff <0 : s1 , s2 = s2 , s1
    is_changed = False
    
    if abs(len_diff)>1 :
        return False

    j = 0
    for i in range(len(s1)):
        if s1[i] != s2[j] :
            if is_changed : return False
            is_changed = True
            if len_diff ==0 :
                j +=1
        else :
            j +=1
    return True