Palindrome

bool isPalindrome( string s )
{
bool result = true;
size_t begin = 0;
size_t end = s.size( ) - 1;
while( begin != end )
{
if (s[begin] != s[end] )
{
result = false;
break;
}
begin++; end--;
}
return( result );
}

This code is on a practice test. Apparently, it will run, but there is a certain bug with it. What would be the fix to fix this bug?
1
2
3
4
5
6
7
bool palindrome( std::string s )
{
    // the string may be empty; we need to take care of that 
    if( s.size() < 2 ) return true ; // *** added: either empty or contains just one character

    // rest of the code 
}
begin may never be equal to end. Consider strings of even length. e.g.
(begin,end) = (0,3) -> (1,2) -> (2,1) -> (3,0) -> trouble

Change
while( begin != end )
to
while( begin < end )

This could also remove the necessity of testing separately for empty strings (provided you make begin and end into int, so that end can hold a negative).
Last edited on
Not the most efficient solution but

 
std::mismatch(std::begin(value), std::end(value), std::rbegin(value), std::rend(value)) == std::end(value);


...basically works for all cases. e.g.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <algorithm>
#include <string>

template<typename T>
static bool is_palindrome(const T& value)
{
	auto it = std::mismatch(std::begin(value), std::end(value), std::rbegin(value), std::rend(value));
	return it.first == std::end(value);
}

int main()
{
	using namespace std::string_literals;
	bool result = is_palindrome("titi"s); // false
result = is_palindrome("aba"s); // true
result = is_palindrome("\0abba"); // true
    return 0;
}


std::distance and std::advance could make this efficient.

Efficient example:

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
36
37
38
39
40
#include <algorithm>
#include <string>

template<typename T>
static bool is_palindrome(const T& value)
{
	auto midPoint = std::end(value);
	const auto distance = std::distance(std::end(value), std::begin(value));
	std::advance(midPoint, distance / 2);
	auto it = std::mismatch(std::begin(value), midPoint, std::rbegin(value), std::rend(value));
	return it.first == midPoint;
}

int main()
{
	using namespace std::string_literals;
	if (!is_palindrome(""s))
		throw 0;
	if (!is_palindrome("a"s))
		throw 0;
	if (!is_palindrome("aa"s))
		throw 0;
	if (is_palindrome("ab"s))
		throw 0;
	if (!is_palindrome("aba"s))
		throw 0;
	if (!is_palindrome("aaa"s))
		throw 0;
	if (is_palindrome("abb"s))
		throw 0;
	if (!is_palindrome("abba"s))
		throw 0;
	if (is_palindrome("abaa"s))
		throw 0;
	if (is_palindrome("aaba"s))
		throw 0;
	if (!is_palindrome("abcba"s))
		throw 0;
    return 0;
}


std::mismatch also has some possible performance advantages if using the execution_policy overloads.
Last edited on
Registered users can post here. Sign in or register to post.