Question

You can edit a string in three different ways: insert, remove or replace a character. Write a function to see if two strings are one or zero edits away.

Example

like, like  --> true (zero edits)
like, likes --> true (one edit: remove/insert)
like, life  --> true (one edit, replace)
like, lik   --> true (one edit: remove/insert)
like, pine  --> false (two edits)
like, lion  --> false (two edits)

Strategy

  1. For most questions that require you to return true or false, you can reduce the scope of the question by removing noise. Often that means exiting early or having conditions that make it impossible to have a true result… Example: If the string lengths differ by 2 or more characters, then you can exit / return an answer.

  2. Try not to solve this problem in one go. Break it down into two checks:

  • Does replacing a character make my strings equal?
  • Does inserting a character make my strings equal?

  1. Keep things simple. See how I avoid adding complex logic by intentionally passing the longer string as first parameter of isOneInsertAway.

  2. Stop caring about things you don’t need. You can find the answer without knowing which character, at which index needs to be replaced. A LOT of questions often can be resolved without caring for a lot of things. Example if you’re solving a question on knowing if there’s a path between A, B. Then you don’t need to care how you got from A to B. You just need to know if there’s a path. Not caring simplifies your thought process. For this reason it’s often good to write down things that don’t matter.

Code

func isOneOrZeroEditsAway(_ str1: String, _ str2: String) -> Bool { 
    let str1 = Array(str1)
    let str2 = Array(str2)
    
    if str1.count == str2.count {
        return isOneReplaceAway(str1, str2)
    } else if str1.count - 1 == str2.count {
        return isOneInsertAway(str1,str2)
    } else if str2.count - 1 == str1.count {
        return isOneInsertAway(str2, str1)
    } else {
        return false
    }
}

/// loop over characters. if difference, bump diff count
/// if at the end the count was more than 1, return false. 
func isOneReplaceAway(_ str1: [Character], _ str2: [Character]) -> Bool {
    
    var diffCount = 0
    for i in 0..<str1.count {
        if str1[i] != str2[i] {
            diffCount += 1
        }
    }
    return diffCount <= 1
}

/// Order matters. `str1` is always one character longer
/// if character is equal, then proceed
/// if not equal, then just move index on `str1` and continue comparing...
func isOneInsertAway(_ str1: [Character], _ str2: [Character]) -> Bool {
    
    var diffCount = 0 
    for i in 0..<str2.count {
        if str1[i + diffCount] != str2[i] {
            diffCount += 1
        }
    }
    return diffCount <= 1
}

It took me a while to understand that the following are interchangeable: “OneInsertAway” and “OneRemoveAway”.

  • “OneInsertAway” is about inserting one character to the shorter string
  • “OneRemoveAway” is about removing one character from the longer string.

Either way works. It’s just these difference of approaches or possibilities that puts me off some times.

Tests

print(isOneOrZeroEditsAway("like", "like")) // true
print(isOneOrZeroEditsAway("like", "likes")) // true
print(isOneOrZeroEditsAway("like", "life")) // true
print(isOneOrZeroEditsAway("like", "lik")) // true
print(isOneOrZeroEditsAway("like", "pine")) // false
print(isOneOrZeroEditsAway("like", "lion")) // false

Complexity

Obviously O(n) where n is the length of the shorter string.

This question falls under the category of Edit Distance