Cracking the Coding Interview — 1.5 One Away

Question

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

Answer 1

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);
}

Answer 2

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);
}

Answer 3

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