5
\$\begingroup\$

I'm posting a solution for LeetCode's "Count Substrings That Differ by One Character". If you'd like to review, please do. Thank you!

Problem

Given two strings s and t, find the number of ways you can choose a non-empty substring of s and replace a single character by a different character such that the resulting substring is a substring of t. In other words, find the number of substrings in s that differ from some substring in t by exactly one character.

For example, the underlined substrings in "computer" and "computation" only differ by the 'e'/'a', so this is a valid way.

Return the number of substrings that satisfy the condition above.

A substring is a contiguous sequence of characters within a string.

Example 1:

enter image description here

Example 2:

enter image description here

Constraints:

  • 1 <= s.length, t.length <= 100
  • s and t consist of lowercase English letters only.

Code

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

static const size_t getCounts(
    const char *source,
    const char *target,
    size_t s_index,
    size_t t_index
) {
    size_t counter = 0;
    size_t prev = 0;
    size_t curr = 0;

    while (s_index < strlen(source) && t_index < strlen(target)) {
        ++curr;

        if (source[s_index] != target[t_index]) {
            prev = curr;
            curr = 0;
        }

        counter += prev;
        ++s_index;
        ++t_index;
    }

    return counter;
}

static const int countSubstrings(
    const char *source,
    const char *target
) {
    size_t counters = 0;

    for (size_t s_index = 0; s_index < strlen(source); ++s_index) {
        counters += getCounts(source, target, s_index, 0);
    }

    for (size_t t_index = 1; t_index < strlen(target); ++t_index) {
        counters += getCounts(source, target, 0, t_index);
    }

    return counters;
}

int main() {
    printf ("%i \n", countSubstrings("aba", "baba"));
    printf ("%i \n", countSubstrings("ab", "bb"));
    printf ("%i \n", countSubstrings("a", "a"));
    printf ("%i \n", countSubstrings("abe", "bbc"));
    printf ("%i \n", countSubstrings("abeaskdfjpoirgfjifjwkdafjaksld",
                                     "fqowuerflqfdjcasdjkvlfkjqheofkjsdjfasldkf"));
    return 0;
}

Outputs:

6 
3 
0 
10 
1314 
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Your examples do not really help because the underlines are not visible (at least not in my browser). \$\endgroup\$ – Martin R Nov 3 '20 at 20:07
3
\$\begingroup\$

It looks nice, and you got the right algorithm.

Still, there are problems and additional ideas:

  1. The const-qualifier on the two functions return-value is ignored. Didn't your compiler warn?

  2. Denoting the start of a string-slice by pointer to start of the whole string and offset into it is cumbersome and inefficient. Just give a pointer to the start of the slice.

  3. You are playing Shlemiel The Painter with all four strlen()-calls in your loops. The compiler might be able to hoist it four you, or it might not.

    If it cannot, at least those in countSubstrings() are cheaper by some constant factor than the calls to a fixed getCounts(), and thus don't influence your codes big-oh.
    But those in getCounts() turn the function from linear to quadratic, and thus the algorithm from quadratic to cubic.

    What I don't get is why you ask for the strings length at all.
    Just substitute !s[n] for strlen(s) == n.

  4. Either int is always big enough, and should be used throughout, or it isn't, and you have to play it safe by using size_t.

  5. By the way, the problem is symmetric in its two arguments. That can be used.

And that was all I found.

static int getCounts(const char* a, const char* b) {
    int prev = 0;
    int curr = 0;
    int r = 0;
    for (; *a && *b; r += prev) {
        ++curr;
        if (*a++ != *b++) {
            prev = curr;
            curr = 0;
        }
    }
    return r;
}

static int manyCounts(const char* a, const char* b) {
    int r = 0;
    while (*a)
        r += getCounts(a++, b);
    return r;
}

int countSubstrings(const char * a, const char * b) {
    return !*a ? 0 : manyCounts(a + 1, b) + manyCounts(b, a);
}
\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.