Removing Specific Characters from Strings

I have an algorithm which parses a string to test for a palindrome. Essentially what I want to do is see if the first and last characters of the string are equivalent. If this is the case, then I would want to remove the first and last characters of the string and pass that string to the function again in a recursive call.

Code:

bool isPalindrome(string inString)
{
	// variable declarations
	char firstChar = inString.at(0); // the first character in the string
	char lastChar = inString.at((int)inString.length()); // the last character in the string
	int stringLength = (int)inString.length(); // the length of the string (num of chars)
	string::iterator firstCharI = inString.begin(); // iterator beginning of the string
	string::iterator lastCharI = inString.end(); // iterator ending of the string
	
	if (inString == "" || stringLength == 1)
		return (true);
	else if (firstChar == lastChar)
	{
		// hack off the first and last characters of the string
		inString.erase(firstCharI);
		inString.erase(lastCharI);
		
		// recursive call to isPalindrome
		return (isPalindrome(inString));	
	}
	else
		return (false);
}

Now I've run into a few issues with this code. First I think I'm preforming a bit of overkill here with all of the information I've prepared about the argument inString. I'm primarily pointing at the iterators. But I found that to use the more suitable overridden version of the erase method uses an iterator for single characters. But that really isn't the primary issue.

The program that this method is coded into compiles fine however when I run the program, with the method above, I get an exception thrown std:ut_of_range which I'm guessing has to do with requested access to an element outside of array bounds, similar to a segmentation fault. Once I got that error, I modified this line in the isPalindrome method:

Code:

char lastChar = inString.at((int)inString.length());

to this:

Code:

char lastChar = inString.at((int)inString.length() - 1);

The program compiled fine however execution terminated with a segmentation fault. I'm not exactly sure why I'm getting this error and I'm not exactly sure how to go about fixing it. If I could have some advice on clearing up this issue I'd appreciate it. Thanks in advance.

inString.end() points to one spot past the last character. erasing it doesn't do anything. change that to inString.end()-1 so that it matches inString.length()-1. there's another problem where you try to index the string out of bounds if it's a palindrome. at the end it becomes an empty string but you still try to index at 0 and length()-1. you can fix that by doing the length test first then getting your indexes and iterators.

Code:

bool isPalindrome(string inString)
{
    int stringLength = (int)inString.length();
    if (inString == "" || stringLength == 1) return (true);
    char firstChar = inString.at(0);
    char lastChar = inString.at(stringLength-1);
    string::iterator firstCharI = inString.begin();
    string::iterator lastCharI = inString.end()-1;
    if (firstChar == lastChar)
    {
        inString.erase(lastCharI);
        inString.erase(firstCharI);
        return (isPalindrome(inString));	
    }
    else return (false);
}

Of course, you could avoid erasing the string, and just call the next level of isPalindrome() with instring.substr(2, length-2)

--
Mats

Code:

bool isPalindrome(string inString)

Code:

inString.erase(firstCharI);
inString.erase(lastCharI);

Code:

return (isPalindrome(inString));

Yog Sothoth!

This has got to be the worst implementation of this algorithm ever.

For a nice big string like this you will allocate a total of 24613 bytes over 151 allocations copying 22650 characters from 151 'std::string' objects..stcejbo 'gnirts::dts' 151 morf sretcarahc 05622 gniypoc snoitacolla 151 revo setyb 31642 fo latot a etacolla lliw uoy siht ekil gnirts gib ecin a roF

Anyway, you have a few problems:

1) In C++ arrays and most types implementing '$ operator [] (?)', including 'std::string', are zero based.

2) The 'erase' method of 'std::string' may invalidate iterators other than the one targeting the element erased.

3) (I'm not sure about this one. It works this way in my library.) The iterator returned by 'container.end()' is not a valid iterator. Using an invalid iterator, including incrementing or decrementing it through addition and subtraction, may yield an invalid iterator.

Soma

If it has to be recursive in the first place. And if it has to be, you don't even need a substring: you could just pass a pair of iterators or the string by reference together with a pair of indices showing where you have reached thus far.

The iterator returned by 'container.end()' is not a valid iterator. Using an invalid iterator, including incrementing or decrementing it through addition and subtraction, may yield an invalid iterator.

I was under the impression that it would be invalid to dereference the end() iterator, but you can decrement it safely to get to the last but one (provided the container is not empty). In any case there are also reverse iterators, but again I was under the impression that the iterator returned by rbegin under the hood points to end(), except that when dereferenced it accesses the previous item (otherwise iterator returned by rend() would have nowhere to point). But I may be mistaken.