Как заставить эту рекурсивную функцию проверять, является ли строка палиндромом? - PullRequest
Новая
       62

Как заставить эту рекурсивную функцию проверять, является ли строка палиндромом?

0 голосов
/ 03 февраля 2020

Функция должна перевернуть строку и вернуть true, если она одинакова в прямом и обратном направлении. Я должен использовать рекурсию для этого, и не могу использовать reverse() для этого. Я прогнал свой код через отладчик, и кажется, что мой код возвращает false, когда он проверяет s == reverse.

Вот моя попытка: 

bool Palindrome(const string& s, int i){
string reverse;

    if(i < s.size()){
        reverse[i] = s[s.size()-(i+1)]; // first character in reverse is the last character in s
        Palindrome(s, i + 1);
        }       
    if(s == reverse){
        return true;
    }
    else{
        return false;
    }

}

Ответы [ 2 ]

0 голосов
/ 03 февраля 2020

Если вы хотите, чтобы Palindrome(const string&) манипулировал string reverse, вы должны передать его по ссылке. 

#include <string>
#include <iostream>

using namespace std;

bool palindrome_internal( const string& s, string& reverse, int i )
{
    if(i < s.size()){
        reverse[i] = s[s.size()-(i+1)]; // first character in reverse is the last character in s
        palindrome_internal( s , reverse , i + 1);
    }

    return s == reverse;
}

bool Palindrome(const string& s ){
    string reversed { s }; // initialized here

    return palindrome_internal( s , reversed , 0 ); // And passed to recursive function
}

int main()
{
    cout << Palindrome( "example" ) << endl; // Not palindrome
    cout << Palindrome( "repaper" ) << endl; // Palindrome
    cout << Palindrome( "rotator" ) << endl; // Palindrome
    cout << Palindrome( "madam" ) << endl; // Palindrome
    cout << Palindrome( "" ) << endl; // Palindrome
    cout << Palindrome( "" ) << endl; // Palindrome
}

онлайн-код

Ваш код на самом деле немного странный потому что вы не вычисляете палиндром рекурсивно, фактически вы заполняете string reverse рекурсивно.

Возможно, эта более простая версия подходит лучше. 

#include <string>
#include <iostream>

bool palindrome( const std::string& s, int i = 0 )
{
    if ( i == s.size() )
        return true;

    return s[ i ] == s[ s.size() - i - 1 ] && palindrome( s , i + 1 );
}

int main()
{
    using namespace std;
    cout << palindrome( "example" ) << endl; // Not palindrome
    cout << palindrome( "repaper" ) << endl; // Palindrome
    cout << palindrome( "rotator" ) << endl; // Palindrome
    cout << palindrome( "madam" ) << endl; // Palindrome
    cout << palindrome( "" ) << endl; // Palindrome
    cout << palindrome( "a" ) << endl; // Palindrome
}

онлайн-код

0 голосов
/ 03 февраля 2020

Следующий код показывает пример реализации того, что вы разработали в вопросе. Он создает обратную строку с использованием рекурсии, а затем сравнивает ее со справочной строкой и возвращает логический результат.

Сложность памяти O (n). Но на самом деле это требует дополнительной памяти O (n) для перевернутой строки. 

#include <iostream>
#include <algorithm>
using namespace std;

bool isPalindrome(string& reference, string& reversed, int index){
    if(index >= reference.size()/2){
        return reference == reversed;
    }

    int lastIndex = reference.size()-1;
    swap(reversed[index], reversed[lastIndex-index]);
    return isPalindrome(reference, reversed, index+1);
}

int main() {
    string ref = "abcdcba";
    string test = ref;
    cout << isPalindrome(ref,test,0) << endl;
    return 0;
}
...