# Cracking the Coding Interview — 1.5 One Away

I would like to know any suggestions about to improve my code solution and your rating of my approach to the problem, I based my code on the fact that if the strings have different length removing one character from the longer string is equal to add one character to the shorter one.

Description

One away : There are three types of edits that can be performed on strings: insert a character, remove a character and replace a character. Given two strings, write a function to check if they are one edit (or zero edits) away.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static int helper_one_way(const char *str1, const char * str2,
size_t len1, size_t flag) {
size_t nchars = 0;
size_t i, j;

for (i = 0, j = 0; i < len1; ++i, ++j) {
if (str1[i] != str2[j]) {
if (++nchars > 1) return 0;
if (flag && i) --i;
}
}
return 1;
}

/* check if str1 can be obtained from string2 adding, deleting, replacing
* at last one char */
int one_way(const char *str1, const char *str2) {
size_t len1 = strlen(str1), len2 = strlen(str2);
size_t diff = abs(len1 - len2);

if (diff > 1) return 0;
if (!diff) return helper_one_way(str1, str2, len1, 0);
if (len1 > len2) return helper_one_way(str2, str1, len2, 1);
return helper_one_way(str1, str2, len1, 1);
}

int main(void) {
printf("%d\n", one_way("pale", "ple"));
printf("%d\n", one_way("pales", "pale"));
printf("%d\n", one_way("pale", "bale"));
printf("%d\n", one_way("pale", "bake"));
return 0;
}

• adding, deleting, removing what is the difference between the latter two items? – greybeard Jul 11 at 2:29
• @greybeard: I meant replacing but I wrote removing, I updated my post. – dariosicily Jul 11 at 14:37

Generally nice code: easy to read, good use of const char* for the string arguments.

It's great that we have unit tests; we can improve them by making them self-checking:

/* return number of test failures (0 or 1) */
int test_one_away(const char *str1, const char *str2, int expected)
{
const int actual = one_way(str1, str2);
if (actual == expected)
return 0;
fprintf(stderr, "one_way \"%s\", \"%s\" expected %d but got %d\n",
str1, str2, expected, actual);
return 1;
}

int main(void)
{
return
+ test_one_away("pale", "ple", 1)
+ test_one_away("pales", "pale", 1)
+ test_one_away("pale", "bale", 1)
+ test_one_away("pale", "bake", 0);
}


We should add some more tests. When I start writing tests (usually before the production code) I usually write the very simplest tests first, probably passing NULL to exercise the error recovery. I'm going to assume that the code won't be testing for null pointers, but would certainly start with the next simplest case: are two empty strings within one change:

        + test_one_away("" "", 1)


Then compare one- and two-character strings against the empty string, and for strings that differ by one or two deletions at the beginning, middle and end. A good guideline for testing functions that return a boolean value is to identify the boundaries where the result should change between false and true (e.g. remove one character from the front ⇒ true; remove two characters from front ⇒ false) and write one test for each side of that transition.

Here's a test that exposes a bug in the code:

        + test_one_away("pale", "ale", 1)


This is because we don't accept deletion of the first character:

        if (flag && i) --i;


The fix is to remove the second part of the condition (remember, unsigned overflow is well-defined, and will exactly match the ++i in the loop increment):

        if (flag) --i;


I'm not sure why flag needs to be a size_t; a simple int should be sufficient. If/when we have access to a C99 compiler (which should be soon; it's around 20 years old now), we could include <stdbool.h> and make it a bool. It also needs a better name; I had to look to the call site to understand what it's for (it seems that a true value means that we're looking for a deletion rather than a replacement).

The conditions in the wrapper function could be expressed more clearly with a single switch on the difference in length:

/* check if str1 can be obtained from string2 adding, deleting, removing
* at last one char */
bool one_way(const char *str1, const char *str2)
{

size_t len1 = strlen(str1);
size_t len2 = strlen(str2);

switch (len2 - len1) {
case (size_t)-1: return helper_one_way(str2, str1, len2, true);
case 0:          return helper_one_way(str1, str2, len1, false);
case 1:          return helper_one_way(str1, str2, len2, true);
default:         return false;
}
}


We don't need to pass the length to helper_one_way, because it can simply stop when it reaches the terminating null char:

    for (i = 0, j = 0;  str1[i];  ++i, ++j) {


Given that we're iterating over strings, it's more idiomatic to use a char pointer than to repeatedly index into the string (though a good compiler ought to generate the same code):

static bool helper_one_way(const char *a, const char *b,
bool allow_deletion)
{
size_t nchars = 0;
while (*a) {
if (*a++ != *b++) {
if (++nchars > 1) return false;
if (allow_deletion) --b;
}
}
return true;
}


Finally: the name - should one_way be spelt one_away?

# Modified code

Applying the above suggestions, we get:

#include <stdbool.h>
#include <string.h>

static bool helper_one_away(const char *a, const char *b,
bool allow_deletion)
{
size_t nchars = 0;
while (*a) {
if (*a++ != *b++) {
if (++nchars > 1) return false;
if (allow_deletion) --b;
}
}
return true;
}

/* Return true if a can be obtained from string2 by adding,
deleting, or removing at most one character */
bool one_away(const char *a, const char *b)
{
switch (strlen(a) - strlen(b)) {
case (size_t)-1: return helper_one_away(b, a, true);
case 0:          return helper_one_away(a, b, false);
case 1:          return helper_one_away(a, b, true);
default:         return false;
}
}

/* Test code */

#include <stdio.h>

/* return number of test failures (0 or 1) */
static int test_one_away(const char *a, const char *b,
bool expected)
{
const int actual = one_away(a, b);
if (actual == expected)
return 0;
fprintf(stderr, "one_away \"%s\", \"%s\" expected %d but got %d\n",
a, b, expected, actual);
return 1;
}

int main(void)
{
return
+ test_one_away("", "", true)
+ test_one_away("", "a", true)
+ test_one_away("pale", "", false)
+ test_one_away("pale", "le", false)
+ test_one_away("pale", "ale", true)
+ test_one_away("pale", "pale", true)
+ test_one_away("pale", "pal", true)
+ test_one_away("pale", "pa", false)
+ test_one_away("pale", "ple", true)
+ test_one_away("ple", "pale", true)
+ test_one_away("pales", "pale", true)
+ test_one_away("pale", "bale", true)
+ test_one_away("pale", "bake", false);
}

• Great review, just one question: how you chose the strings being tested in the main() ? – dariosicily Jul 11 at 15:39
• Partly by reading the implementation ("I wonder if we've tested that line when flag is true and i is zero?") and partly by experience of known problem cases (empty strings, one-character strings). The rest were just copied uncritically from the original. For completeness, it might be worth having a test with a change (rather than insert/delete) of the first character, and of the last character. – Toby Speight Jul 11 at 15:44
• Also, checking boundary conditions, where the result should flip from one to the other (e.g. remove one character from the front ⇒ true; remove two characters from front ⇒ false; no need to test three chars at front). – Toby Speight Jul 11 at 15:51
1. Using a size_t for a boolean flag, and calling it flag, is nearly an obfuscation. Use int pre-C99 and call it something descriptive like substitute.

2. strlen() is likely a waste, though it makes describing the algorithm easier. Try to do without the additional iteration.

3. Getting the length of the longest common prefix looks like a well-defined task which can be extracted, and a useful building-block. Do so.

4. one_way, one_away, or one_microsoft_way? Having a properly-spelled correctly-selected name is Always very important.

5. Change to a single-traversal algorithm:

Remove the common prefix.

Measuring the common prefix without the first characters is quite instructive.

With x and y different from a, call n = strlen_common(++a, ++b):

1. At most one substitution at the start:

xaaaabcde
yaaaabcde


Result n == 8, a[n] == b[n].

2. Deletion from the first:

xaaaabcde
aaaabcde


n == 3, strcmp(a + n, b + n - 1) != 0

3. Same way for deletion from second.

The modified code (also live on coliru):

size_t strlen_common(const char* a, const char* b) {
size_t r = 0;
while (*a && *a++ == *b++)
++r;
return r;
}

int one_away(const char* a, const char* b) {
size_t n = strlen_common(a, b);
a += n;
b += n;
if (!*a++)
return !*b || !b[1];
if (!*b++)
return !*a;
n = strlen_common(a, b);
return a[n] == b[n]
|| !strcmp(a + n - 1, b + n)
|| !strcmp(a + n, b + n - 1);
}

• Great review, as you described in the second point I will try your version without calling strlen(). – dariosicily Jul 11 at 15:45

This is more of a suggestion on substance than a review of the code style; I'll leave that for other reviewers.

Your solution looks pretty good to me. I think you could streamline it a bit by doing it all in one shot, without checking the length of the strings first. For example:

int one_way(const char *a, const char *b)
{
int misses = 0, ia = 0, ib = 0, missed_index = 0;
while (a[ia] || b[ib]) {
/* Characters at this position match? Keep going... */
if (a[ia] == b[ib]) {
if (a[ia]) ++ia;
if (b[ib]) ++ib;
/* Mismatched characters? */
} else {
/* Already missed once; backtrack if skipped earlier, or bail. */
if (++misses > 1) {
if (missed_index) {
ia = missed_index;
ib = missed_index;
missed_index = 0;
}
else return 0;
/* No misses yet... */
} else {
/* Skip buffer A ahead if its next char matches buffer B. */
if (a[ia] && a[ia + 1] == b[ib]) {
++ia;
missed_index = ia;
}
/* Skip buffer B ahead if its next char matches buffer A. */
if (b[ib] && b[ib + 1] == a[ia]) {
++ib;
missed_index = ib;
}
/* Skip both buffers ahead, if neither was skipped. */
if (!missed_index) {
if (a[ia]) ++ia;
if (b[ib]) ++ib;
}
}
}
}
return 1;
}



You can test it out here: https://onlinegdb.com/B1C76fNZS

• Try "aa" and "ba". Sorry I gave you the wrong test-case. – Deduplicator Jul 10 at 22:43
• @Deduplicator thanks for catching that, had a feeling this wasn't quite complete. I think you could probably add something like this to let the other iterator "catch up" after this situation happens: beta.pastie.org/iH3jbXzFRKhh ... but it's not exactly model clean code at this point. Will think about this a bit and edit or remove this answer later. – user11536834 Jul 10 at 23:11
• I took a different approach which also resulted in a single traversal. – Deduplicator Jul 10 at 23:28
• @Deduplicator I think it's fixed now, but I'm not even sure at this point. I like your solution better now that this one's gotten hairy; yours is actually closer to what I had in mind initially. – user11536834 Jul 11 at 0:40