Programming Problem: Single-Edit Difference
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
C#
Java
C++11 console
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