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