Article #5 in a 9-part series.

1 - Programming Problem: Determine if Two Strings Are Anagrams
2 - Programming Problem: Sum-Zero Triplet
3 - Programming Problem: Palindromes
4 - Problem: Validate a Phone Number
5 - this article
6 - Prime Factors Problem 1: LCM
7 - Prime Factors Problem 2: Largest Prime Factor
8 - How-To: Substrings in Swift
9 - Programming Problem: Pangram

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#: 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;
}

Article #5 in a 9-part series.

1 - Programming Problem: Determine if Two Strings Are Anagrams
2 - Programming Problem: Sum-Zero Triplet
3 - Programming Problem: Palindromes
4 - Problem: Validate a Phone Number
5 - this article
6 - Prime Factors Problem 1: LCM
7 - Prime Factors Problem 2: Largest Prime Factor
8 - How-To: Substrings in Swift
9 - Programming Problem: Pangram