One Edit Distance

One Edit Distance

문제 내용

두개의 문자열을 비교해서 단 하나의 차이점만 있을경우 true

차이점이 없거나 2개 이상의 차이점이 없으면 false를 return하라

 

접근 방법

일단 즉각적으로 문제를 해결할 수 있는 경우 2가지를 처리한다.

• 두 words의 length가 2이상 차이 나는가?
• 두 words는 같은가?

이 2가지가 문제가 없다면

다음과 같은 2가지로 나뉠수 있다.

• 2개의 words의 length는 같다
• 2개중 하나의 word의 length가 + 1 길다

2개의 words중 length가 같은 경우

답이 될 수 있는 경우는 단 한가지 경우밖에 없다.

특정 지점에서 양쪽의 value가 달라야 한다.

상기의 예를 보면 c와 b가 달라지는 지점을 찾았고, 이후의 두개의 value ee,ee는 무조건 같아야 한다.

다르나면 false이다.

그럼 한쪽이 더 길면 어떨까?

더 긴곳의 위치만 +1을 추가하고 나머지 길이가 동일해야 한다.

마지막으로 

aee까지 모두 같은 값이 있고 마지막 한자리만 다르다면 true를 return 하면 된다.

One Pass 입으로 Time Complexity는

$$ O(N) $$

이다.

var isOneEditDistance = function(s, t) {
    if(1 < Math.abs(s.length - t.length)) return false;
    if(s === t) return false;
    
    if(s.length < t.length) return isOneEditDistance(t,s); //s를 더 길게하고 t를 짧게 잡는다.
    
    for(let i = 0; i < Math.min(s.length,t.length); i++){
        if(s.charAt(i) !== t.charAt(i)){
            
            if(s.length === t.length){
                return s.substring(i+1,s.length) === t.substring(i+1,t.length); // 같으면 true 다르면 false
            } else {
                return s.substring(i+1,s.length) === t.substring(i,t.length); //같으면 true 다르면 false
            }
        }
    }
    
    return true;
    
};