[Kotlin] 두개의 String이 있다고 했을 때, 하나의 String에 대해 문자를 하나 이하로 추가하거나 지우거나 다른 값으로 바꾸었을 때 동일한지 확인

문제

 두개의 String이 있다고 했을 때, 하나의 String에 대해 문자를 하나 이하로 추가하거나 지우거나 다른 값으로 바꾸었을 때 동일한지 확인

- "abcd", "abc" 이면 문자 하나가 차이나므로 true반환

- "abcd", "acbd" 이면 문자가 2개를 바꿔야 하므로 false 반환

 

문제 풀기 전 확인 사항

1. 공백이 있는지 확인해야 함. 공백은 없음

2. 대소문자 구분이 있는지 확인해야 함. 대소문자 구분 있음

 

문제 풀이1

첫 문제풀이는 문제 풀이의 경우를 세가지로 나눈다.

1. 문자열의 길이가 같은 경우

2. 문자열의 길이가 1 차이 나는 경우

3. 문자열의 길이가 2 이상 차이 나는 경우

 

각 방식은 다음과 같이 구현한다.

1. 문자열의 길이가 같은 경우 - 포인터를 1씩 증가시키면서 둘이 다른게 나오면 문자 교체한다고 가정하고 count를 1증가. count가 1 이하일 경우 true 반환

2. 문자열의 길이가 1 차이 나는 경우 - 포인터를 1씩 증가시키면서 둘이 다른게 나오면 짧은 길이의 포인터만 1 증가시키고 count를 1증가. count가 1 이하일 경우 true 반환

3. 문자열의 길이가 2 이상 차이 나는 경우 - false 반환

class Solution2() {
    fun checkOneEdit(string1: String, string2: String): Boolean {
        return when {
            string1.length == string2.length     -> {
                checkReplaceNeeded(string1, string2)
            }

            string1.length - 1 == string2.length -> {
                checkOneEditNeeded(string1, string2)
            }

            string1.length == string2.length - 1 -> {
                checkOneEditNeeded(string2, string1)
            }

            else                                 -> {
                false
            }
        }
    }

    private fun checkReplaceNeeded(string1: String, string2: String): Boolean {
        var pointer1 = 0
        var pointer2 = 0
        var count = 0
        while (pointer1 < string1.length && pointer2 < string2.length) {
            if (string1[pointer1] != string2[pointer2]) {
                count += 1
            }
            pointer1 += 1
            pointer2 += 1
        }

        return count <= 1
    }

    private fun checkOneEditNeeded(longerString: String, shorterString: String): Boolean {
        var longPointer = 0
        var shortPointer = 0
        var count = 0

        while (longPointer < longerString.length && shortPointer < shorterString.length) {
            if (longerString[longPointer] == shorterString[shortPointer]) {
                longPointer += 1
                shortPointer += 1
                continue
            } else {
                longPointer += 1
                count += 1
            }
        }
        return count <= 1
    }
}

 

복잡도

문자열의 길이를 N, M이라 할 때,

시간 복잡도 : O(min(N,M)) - 포인터가 이동하는 시간만 계산한다. String은 항상 문자열의 길이 정보를 유지하고 있기 때문

공간 복잡도 : O(1) - 상수개의 pointer와 count에 대한 정보만 유지한다.

 

 

문제 풀이2

 

class Solution() {
    fun checkOneEdit(string1: String, string2: String): Boolean {
        var longPointer = 0
        var shortPointer = 0

        var count = 0

        var longerString = ""
        var shorterString = ""
        var lengthDifference = 0

        if (string1.length > string2.length) {
            lengthDifference = string1.length - string2.length
            longerString = string1
            shorterString = string2
        } else {
            lengthDifference = string2.length - string1.length
            longerString = string2
            shorterString = string1
        }

        if (lengthDifference >= 2) return false

        while (true) {
            if (longPointer >= longerString.length) break
            if (shortPointer >= shorterString.length) break

            if (longerString[longPointer] == string2[shortPointer]) {
                longPointer += 1
                shortPointer += 1
                continue
            } else {
                shortPointer += 1
                count += 1
                continue
            }
        }

        return count <= 1
    }
}

 

 

복잡도

문자열의 길이를 N, M이라 할 때, 

시간 복잡도 : O(min(N,M)) - 포인터가 이동하는 시간만 계산한다. String은 항상 문자열의 길이 정보를 유지하고 있기 때문

공간 복잡도 : O(1) - pointer 두개와 count에 대한 정보만 유지한다. String은 플라이웨이트 패턴을 사용하므로 한 번 할당되면 두 번 할당되지 않는다.

 

 

테스트 케이스

fun main() {
    val solution = Solution()
    println(solution.checkOneEdit("acc", "abc")) // 같은 길이 - 하나만 다른 경우 - true
    println(solution.checkOneEdit("aab", "ac")) // 다른 길이 - 길이 하나 차이 - 문자 하나 차이 - false
    println(solution.checkOneEdit("aac", "ac")) // 다른 길이 - 길이 하나 차이 - 문자 하나 차이 - true
    println(solution.checkOneEdit("abc", "ab")) // 다른 길이 - 길이 하나 차이 - 문자 하나 차이 - true
    println(solution.checkOneEdit("abc", "a")) // 다른 길이 - 길이 두개 차이 false - false
    println(solution.checkOneEdit("", "")) // 같은 길이 - empty String - true
}