The bugs are rather subtle. You changed M and N so your recursive calls AFTER DOING THAT are nonsense, and bungle your result. You also were returning true when N was too small, but on the recursive calls, that is not correct as those calls imply a state of false coming in, so unless it goes into the loop, it needs to return false on those.
With some modifications to account for that problem:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
|
bool isKdrom(char * M, int N, int k)
{
char* mcpy{M};
int ncpy{N};
if(N < 2) return false;
bool result{true};
while (N >=1 )
{
result &= M[0] == M[N-1];
M++; N-=2;
}
M = mcpy;
N = ncpy;
if (result) return true;
if (k > 0)
return isKdrom(M+ 1, N-1, k-1) || isKdrom(M, N-1, k-1);
return false;
}
int main()
{
cout << std::boolalpha;
char c[] = "12321";
char c2[] = "1221";
char c3[] = "123";
char c4[] = "123219";
cout << isKdrom(c,strlen(c), 2)<<endl;
cout << isKdrom(c2,strlen(c2),2)<<endl;
cout << isKdrom(c3,strlen(c3),2)<<endl;
cout << isKdrom(c4,strlen(c4),2)<<endl;
}
|
this may not be 100% correct even now. But its closer. It will NOT return true for initial strings of length 1, which is not technically correct ("x" is a trivial drome). To fix that you would need to tie result bool back into the recursion so it is aware of 'first call exception' somehow. Another sneaky way to do that is to add a default parameter to the end. The recursive calls can put a value there, the user will only have the default. The default will then indicate first time exception:
bool isKdrom(char * M, int N, int k, bool first = true)
{
if(first && N == 1) return true;
blah, blah
return isKdrom(M+ 1, N-1, k-1, false) || ...
}
main()
isKdrom(c,strlen(c),2); //leave last parameter empty here!
I fixed it with the 'bandaid' approach so you can SEE what was wrong with it clearly.
the right thing to do is a rewrite that cleans this mess up, with the new ideas in place and such.