Problem 🤔

There are 3 types of edits that can be performed on strings:

1. insert a character
2. remove a character
3. replace a character

Given 2 strings, write a function to check if they are 1 (or 0) edits away.

Example 1

pale, ple -> True

pales, pale -> True

pale, bale -> True

pale, bake -> True

Real World Applications 🌎

Spellcheckers are great, right?!

Have you ever wondered how they know to recommend words when you’re making a typo? Of course there are much fancier algoriths and strategies than this, but think of this as a naive implementation!

The Finer Details 🔎

Let’s try and formulate the 3 types of edits into rules we can check for.

1) String lengths difference is more than 1

• We can’t delete more than 1 char. We are not 1 edit away!

2) Strings are identical length

• 1 replacement is allowed! Anything else and we’re not 1 edit away.

3) String lengths differ by 1

• We can do 1 deletion! We’d delete from the longer string!

We’ve mapped out all the cases, now let’s write them out.

Solution 💡

Complexity Analysis 🧮

Time complexity

O(min(n, m))

We’ll iterate over the shorter of the strings!

Space complexity

O(1)

No additional memory allocated.

Takeaways 🎉🥳

• Take your time before beginning to code! Coding this up is easy after we wrote out the categories!

Resources 📚 💻

Cracking the Coding Interview, CTCI, Chapter 1, Arrays and Strings, 1.5