Я хочу, чтобы мой второй оператор if выполнял цикл рекурсивного типа, но он ничего не возвращает и по умолчанию принимает значение false. Что я делаю не так?
bool isPalindrome(string some_string) {
if (some_string.length() == 0 || some_string.length() == 1) {
return true;
}
if (some_string[0] == some_string[some_string.length() - 1]) {
return isPalindrome(some_string.substr(1, some_string.length() - 1));
}
else {
return false;
}
}
Прежде всего, этот код проверяет, является ли строка палиндромом или нет. Я просмотрел несколько ссылок и подумал, что могу использовать substr для получения символов после первого индекса и перед последним индексом символов. Что я делаю не так? Я здесь впервые, поэтому прошу прощения, если этот вопрос был не совсем правильно задан.
Тактическое примечание: создание новых strings может оказаться очень дорогим. Лучше передать string по ссылке, а вместе с ней передать индексы начала и конца интересующей области.
Добавьте std::cout << some_string << '\n'; в начало вашей функции, и вы сможете увидеть, что такое some_string, и это должно точно сказать вам, в чем проблема.
substr занимает позицию и отсчитывает (длину), а не начальную и конечную позицию. Что это говорит вам о том, что вы должны передать в качестве второго аргумента?
Примечание: some_string[0] == some_string[some_string.length() - 1] будет немного более читабельным, чем some_string.front() == some_string.back().
Примечание по использованию Stack Overflow: дайте «Как задавать» и «Написание идеального вопроса» для прочтения. Знать, что делает вопрос хорошим, гораздо эффективнее, чем не знать и извиняться.
Поскольку на этот конкретный вопрос есть ответы, отмечу, что рекурсия для решателя палиндромов не обязательна.
Ответы 2
Проблема вашего кода в том, что substr() используется неправильно. Вот ссылка на cppreference с полной документацией об этом методе. Но если говорить простыми словами, проблема в том, что второй аргумент этого метода — это не последний индекс подстроки, а количество символов, которые следует включить в подстроку. Итак, во втором if вы вызываете рекурсию с той же строкой, но без первой буквы. Итак, для строки "abba" будет выполняться isPalindrome("bba") вместо isPalindrome("bb").
Чтобы сделать то, что вы намеревались сделать, вам нужно изменить эту строку:
return isPalindrome(some_string.substr(1, some_string.length() - 1));
вместо этого:
return isPalindrome(some_string.substr(1, some_string.length() - 2));
Для потомков вот реализация с использованием итераторов. Чрезвычайно дешево для длинных струн и очень быстро. В качестве бонуса — всего пять строк кода:
#include <iostream>
#include <string>
bool isPalindrome(std::string::const_iterator begin, std::string::const_iterator end) noexcept;
int main()
{
std::string abba{"amanaplanacanalpanama"};
return isPalindrome(std::cbegin(abba), std::cend(abba));
}
bool isPalindrome(std::string::const_iterator begin, std::string::const_iterator end) noexcept {
if (begin == end) return true;
if (end < begin) return false;
const auto b = *begin;
const auto e = *(end - 1);
return (b == e) ? ( begin != (end - 1) ? isPalindrome(++begin, --end) : true) : false;
}