2
\$\begingroup\$

This is my code to check if a string C is an interleaving of Strings A and B. Please suggests optimizations, and where I can improve.

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include<string.h>

using namespace std;
int isInterleaved(char a[100],char b[100],char c[200],int i, int j, int k)
{
    if(i==0&&j==0)
        return true;
    if(i>=0&&j>=0)
    {

    if(c[k]==a[i]&&c[k]!=b[j])
        return isInterleaved(a,b,c,i-1,j,k-1);
    else if(c[k]==b[j]&&c[k]!=a[i])
        return isInterleaved(a,b,c,i,j-1,k-1);
    else if(c[k]==a[i]&&c[k]==b[j])
        return isInterleaved(a,b,c,i-1,j,k-1)||isInterleaved(a,b,c,i,j-1,k-1);
    else
        return false;
    }
    else
    {
        if(i<0&&j>=0)
        {
            if(c[k]==b[j])
            return isInterleaved(a,b,c,i,j-1,k-1);
            else
                return false;
        }
        if(j<0&&i>=0)
        {
            if(c[k]==a[i])
                return isInterleaved(a,b,c,i-1,j,k-1);
            else
                return false;
        }

    }
}
int main()
{
char a[100],b[100],c[200];
cin>>a;
cin>>b;
cin>>c;
int l1=strlen(a),l2=strlen(b),l3=strlen(c);
if(l3>l1+l2)
    {
        printf("C is not an interleaving of A and B\n");
        return 0;
    }
int ans=isInterleaved(a,b,c,l1-1,l2-1,l3-1);
printf("%d\n",ans);
return 0;
}
\$\endgroup\$
5
\$\begingroup\$

I would rewrite this part of code

if(c[k]==a[i]&&c[k]!=b[j])
    return isInterleaved(a,b,c,i-1,j,k-1);
else if(c[k]==b[j]&&c[k]!=a[i])
    return isInterleaved(a,b,c,i,j-1,k-1);
else if(c[k]==a[i]&&c[k]==b[j])
    return isInterleaved(a,b,c,i-1,j,k-1)||isInterleaved(a,b,c,i,j-1,k-1);
else
    return false;
}

where you are, at the end, testing 2 posible ways to go on, as this

if(c[k]==a[i]) {
     if (isInterleaved(a,b,c,i-1,j,k-1)) return true;
}
if(c[k]==b[j]) {
    if (isInterleaved(a,b,c,i,j-1,k-1)) return true;
}
return false;
\$\endgroup\$
7
\$\begingroup\$

Just about every #include in this code is unneeded. You use cin, strlen and printf. That requires just <cstring>, <cstdio>, and <iostream>. In fact, if you're using C++, you should just use cout as an output stream instead of using printf, which would cut the imports down to <cstring> and <iostream>. The rest should be completely removed.

Why hardcode the array lengths as arguments?

int isInterleaved(char a[100],char b[100],char c[200],int i, int j, int k)

This should be:

int isInterleaved(char *a, char *b, char *c, int i, int j, int k)

Preferably, if you're using C++ and not C, you should instead use std::string (which would need an #include <string>.)

You're using a fairly strange (and inconsistent) brace style:

if(l3>l1+l2)
    {
        printf("C is not an interleaving of A and B\n");
        return 0;
    }

Or no indentation:

if(i>=0&&j>=0)
{

if(c[k]==a[i]&&c[k]!=b[j])
    return isInterleaved(a,b,c,i-1,j,k-1);
else if(c[k]==b[j]&&c[k]!=a[i])
    return isInterleaved(a,b,c,i,j-1,k-1);
else if(c[k]==a[i]&&c[k]==b[j])
    return isInterleaved(a,b,c,i-1,j,k-1)||isInterleaved(a,b,c,i,j-1,k-1);
else
    return false;
}

and

if(c[k]==b[j])
return isInterleaved(a,b,c,i,j-1,k-1);

This makes the code harder to read.

Your code could probably do with some commenting, at least explaining the different cases.

In the end, using some C++ features, I'd do it something like this:

#include <iostream>
#include <string>
#include <iterator>

template <typename Iterator>
bool is_interleaved_impl(Iterator a_begin, Iterator a_end, Iterator b_begin, 
                         Iterator b_end, Iterator c_begin, Iterator c_end)
{
    // Case 1: We've exhausted a, so all we can do is draw the rest of the characters
    // from b, in order.
    if(a_begin == a_end) {
        if(std::distance(b_begin, b_end) != std::distance(c_begin, c_end)) {
            return false;
        }
        return std::string(c_begin, c_end) == std::string(b_begin, b_end);
    }
    // Case 2: We've exhausted b, so all we can do is draw the rest of the
    // characters from a, in order.
    else if(b_begin == b_end) {
        if(std::distance(a_begin, a_end) != std::distance(c_begin, c_end)) {
            return false;
        }
        return std::string(c_begin, c_end) == std::string(a_begin, a_end);
    }
    // Case 3: Characters can be chosen from either a OR b. In this case, we split into
    // 2 possibilities == 2 recurive calls.
    else if(*a_begin == *c_begin && *b_begin == *c_begin) {
        return is_interleaved_impl(a_begin + 1, a_end, b_begin, b_end, c_begin + 1, c_end) ||
               is_interleaved_impl(a_begin, a_end, b_begin + 1, b_end, c_begin + 1, c_end);
    }
    // Case 4: Only the next character from a matches.
    else if(*a_begin == *c_begin) {
        return is_interleaved_impl(++a_begin, a_end, b_begin, b_end, ++c_begin, c_end);
    }
    // Case 5: Only the next character from b matches.
    else if(*b_begin == *c_begin) {
        return is_interleaved_impl(a_begin, a_end, ++b_begin, b_end, ++c_begin, c_end);
    }
    // Nothing matches, so they aren't interleaved.
    return false;
}

bool is_interleaved(const std::string& a, const std::string& b, const std::string& c)
{
    if(a.size() + b.size() != c.size()) {
        return false;
    }
    return is_interleaved_impl(a.begin(), a.end(), b.begin(), b.end(), c.begin(), c.end());
}
\$\endgroup\$
  • 1
    \$\begingroup\$ The two subcalls in case 3 seem like they would pass the wrong values for the begin iterators due to how they use preincrement. I would suggest passing a_begin + 1, b_begin + 1 and c_begin + 1 (or precalculating them) instead. \$\endgroup\$ – Michael Urman Feb 9 '14 at 1:21
  • \$\begingroup\$ @MichaelUrman Good catch. Fixed. \$\endgroup\$ – Yuushi Feb 9 '14 at 6:19
6
\$\begingroup\$

You include a ton of headers you don't use. This is distracting and hurts both reading and compilation time.

The early check for matching size seems like an optimization, but since it's checked every time through the recursion, it's probably harmful. It turns what should be an linear algorithm into a quadratic algorithm as it scans every remaining letter for each letter.

I would probably use character pointers instead of character arrays, and try to use more meaningful names. If you really want to stick with indices instead of character pointers, I would suggest wrapping this in a class that can track the three strings, allowing you to pass only the indices to the recursive call. Here's an untested attempt to implement this with pointers.

// A string is considered interleaved if for each character along `interleaved` you can
// find its character at the front of the remainder of one of the source strings.
// All strings must be c-style zero-terminated strings.
bool isInterleaved(char const *interleaved, char const *source1, char const *source2)
{
    // must terminate at end of `interleaved`
    if (!*interleaved)
        return !*source1 && !*source2

    // check whether front characters of `interleaved` and either source string match
    // and remainders are an interleaved string
    return (*interleaved == *source1 && isInterleaved(interleaved + 1, source1 + 1, source2))
        || (*interleaved == *source2 && isInterleaved(interleaved + 1, source1, source2 + 1));
}

The worst case running time of this approach would be for a call that looks like isInterleaved("aaaaaa...aaaa", "aaaaa...aaaa", "aaaaa...aaab") where it has to check both options in both strings until it finally finds at the end that it never matches. In some cases the early length-based termination could catch this, but in others it cannot.

If you are working with particularly long strings, you may need to use the heap rather than the stack to track the recursive step of the algorithm. This is often done by storing the tuple of three character pointers in a std::stack or std::queue and iterating through that until a match is confirmed or the collection is empty.

\$\endgroup\$
  • \$\begingroup\$ Took me a while to realize that partially overlapping sources requires the recursion. Tnx for pointing that out in my flawed attempt. \$\endgroup\$ – TemplateRex Feb 9 '14 at 8:09

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.