This question is based on a problem found in Cracking the Coding Interview by Gayle Laakmann McDowell which contians nearly 200 problems.

Test if two strings are different by only a single-character edit.

An edit is defined as an inserted character, deleted character, or replaced character. Note that zero edits (same string) counts as a character replacement where the replaced character is the same. In other words, can you add a character, remove a character, or replace a character to result in the other string?

  • “save” and “safe” = true
  • “Mark Henry” and “MaRk Henry” = true
  • “sve” and “save” = true
  • “sve” and “saVe” = false

Give it a try in your preferred language then check out my solution below. In an interview, you may want to quickly go over any assumptions or observations before writing code.

assumptions

  • An empty string is acceptable.
  • The length of a string is manageable and reasonably short for our system.

observations

  • Difference in text length greater than one require more than one edit.
  • Cases to consider: insert, remove, replace.
  • Insert is the same as remove in reverse.

solution

We don’t need to worry about finding where the difference is or total differences. A simple comparison by traversal until our limit is reached will suffice. Of course, there’s the obvious case of both strings being identical which we could check for, but we’ll cover it anyway.

Since insert and remove are the same, we could handle them as a single case and handle replace on its own. Replace isn’t all that different, and in both cases we’ll need to traverse to count differences, so I chose to save repetition for maintainability and reduce length.

Here are my solutions written in Swift, C#, Java, and C++. The Swift solution is for a playground with test strings.


Swift 3

Swift 3: Single-Char-Edit Diff
import Cocoa
func OneEditDiff(text1: String, text2: String) -> Bool
{
// length diff must be < 1
// lenght = 0 is acceptable
if text1.characters.count >= text2.characters.count - 1 && text1.characters.count <= text2.characters.count + 1
{
// the obvious case
//if text1 == text2 { return true}
let char1Arr = Array(text1.characters)
let char2Arr = Array(text2.characters)
var diffCount = 0
var idx1 = 0
var idx2 = 0
while idx1 < char1Arr.count && idx2 < char2Arr.count
{
if char1Arr[idx1] == char2Arr[idx2] {
idx1 += 1
idx2 += 1
}
else {
diffCount += 1
if diffCount > 1 {
return false
}
if char1Arr.count > char2Arr.count {
idx1 += 1
}
else if (char2Arr.count > char1Arr.count) {
idx2 += 1
}
else {
idx1 += 1
idx2 += 1
}
}
}
return true
}
return false
}
OneEditDiff(text1: "pale", text2: "sale")
OneEditDiff(text1: "pale", text2: "save") // false
OneEditDiff(text1: "pale", text2: "pale")
OneEditDiff(text1: "pale", text2: "pales")
OneEditDiff(text1: "pales", text2: "pale")
OneEditDiff(text1: "pale", text2: "pae")
OneEditDiff(text1: "ple", text2: "pale")
OneEditDiff(text1: "pale", text2: "plae") // false
OneEditDiff(text1: "pale", text2: "pals")
OneEditDiff(text1: "", text2: "a")

C#

C#: Single-Char-Edit Diff
bool OneEditDiff(string text1, string text2)
{
if (text1 == null || text2 == null) return false;
// obvious case - let's ignore
//if (text1.Equals(text2)) return true;
// length diff must be < 1
// length = 0 is acceptable
if (text1.Length >= text2.Length - 1 && text1.Length <= text2.Length + 1)
{
int diffCount = 0;
int idx1 = 0;
int idx2 = 0;
while (idx1 < text1.Length && idx2 < text2.Length)
{
if (text1[idx1].Equals(text2[idx2]))
{
idx1++;
idx2++;
}
else
{
diffCount++;
if (diffCount > 1)
{
return false;
}
if (text1.Length > text2.Length)
{
idx1++;
}
else if (text1.Length < text2.Length)
{
idx2++;
}
else
{
idx1++;
idx2++;
}
}
}
return true;
}
return false;
}
}

Java

Java: Single-Char-Edit Diff
static boolean oneEditDiff(String text1, String text2)
{
if (text1 == null || text2 == null) return false;
// obvious case
//if (text1.Equals(text2)) return true;
// length diff must be < 1
// length = 0 is acceptable
if (text1.length() >= text2.length() - 1 && text1.length() <= text2.length() + 1)
{
int diffCount = 0;
int idx1 = 0;
int idx2 = 0;
while (idx1 < text1.length() && idx2 < text2.length())
{
if (text1.charAt(idx1) == text2.charAt(idx2))
{
idx1++;
idx2++;
}
else
{
diffCount++;
if (diffCount > 1)
{
return false;
}
if (text1.length() > text2.length())
{
idx1++;
}
else if (text1.length() < text2.length())
{
idx2++;
}
else
{
idx1++;
idx2++;
}
}
}
return true;
}
return false;
}

C++11 console

C++11: Single-Char-Edit Diff console
#include "stdafx.h"
#include <stdio.h>
#include <iostream>
#include <string>
void TestPairForOneEdit(std::string text1, std::string text2);
bool OneEditDiff(std::string text1, std::string text2);
int main()
{
TestPairForOneEdit("pale", "sale");
TestPairForOneEdit("pale", "save"); // false
TestPairForOneEdit("pales", "pale");
TestPairForOneEdit("pale", "pae");
TestPairForOneEdit("ple", "pale");
TestPairForOneEdit("pale", "plae"); // false
TestPairForOneEdit("pale", "pals");
return 0;
}
void TestPairForOneEdit(std::string text1, std::string text2)
{
if (OneEditDiff(text1, text2))
{
// example output using printf
printf("%s and %s are one-edit away\n", text1.c_str(), text2.c_str());
}
else
{
// example using standard cout
std::cout << text1 << " and " << text2 << " are more than an edit different" << std::endl;
}
}
bool OneEditDiff(std::string text1, std::string text2)
{
// remember: std::string is not a pointer and defaults to empty; can't be null
int len1 = text1.length();
int len2 = text2.length();
// length difference must be < 1
// length = 0 is okay
if (len1 >= len2 - 1 && len1 <= len2 + 1)
{
int diffCount = 0;
int idx1 = 0;
int idx2 = 0;
while (idx1 < len1 && idx2 < len2)
{
if (text1[idx1] == text2[idx2])
{
idx1++;
idx2++;
}
else
{
diffCount++;
if (diffCount > 1)
{
return false;
}
if (len1 > len2)
{
idx1++;
}
else if (len1 < len2)
{
idx2++;
}
else
{
idx1++;
idx2++;
}
}
}
return true;
}
return false;
}