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 &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;string.h&gt;

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 &lt; len1; ++i, ++j) {
        if (str1[i] != str2[j]) { 
            if (++nchars &gt; 1) return 0;
            if (flag &amp;&amp; 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 &gt; 1) return 0;
    if (!diff) return helper_one_way(str1, str2, len1, 0);
    if (len1 &gt; 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;
}
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, &quot;one_way \&quot;%s\&quot;, \&quot;%s\&quot; expected %d but got %d\n&quot;,
            str1, str2, expected, actual);
    return 1;
}


int main(void)
{
    return
        + test_one_away(&quot;pale&quot;, &quot;ple&quot;, 1)
        + test_one_away(&quot;pales&quot;, &quot;pale&quot;, 1)
        + test_one_away(&quot;pale&quot;, &quot;bale&quot;, 1)
        + test_one_away(&quot;pale&quot;, &quot;bake&quot;, 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(&quot;&quot; &quot;&quot;, 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(&quot;pale&quot;, &quot;ale&quot;, 1)

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

        if (flag &amp;&amp; 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 &lt;stdbool.h&gt; 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 &gt; 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 &lt;stdbool.h&gt;
#include &lt;string.h&gt;

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 &gt; 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 &lt;stdio.h&gt;

/* 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, &quot;one_away \&quot;%s\&quot;, \&quot;%s\&quot; expected %d but got %d\n&quot;,
            a, b, expected, actual);
    return 1;
}

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