时间戳

首页 > 解决方案 > 寻找可能的前缀回文

c++ - 寻找可能的前缀回文

问题描述

我们得到一个长度为 N 的字符串 S。我们必须计算可以重新排列成回文的前缀的数量。例如：考虑字符串“abba”——“a”、“abb”和“abba”是可以重新排列成回文的前缀。

我的方法：我尝试使用 XOR 来解决这个问题。例如，如果字符串中所有字符的异或为0，则可以使包含偶数个字符的字符串成为回文。对于具有奇数字符的字符串，所有字符的异或应在97到122之间，即单个字符。

这是我的代码的一部分-

    string s;
    cin>>s;
    int a,n;
    int ans=1;
    n= s.length();
    a=s[0];
    for (int i=1;i<n;i++)
        {
            a=a^(s[i]);
            if (i%2)
            {
                if (a==0)
                {
                    ans++;
                }
            }
            else
            {
                if ((a>=97)&&(a<=122))
                {
                    ans++;
                }
            }
        }
    cout<< ans<< "\n";

我尝试运行，它在某些测试用例中成功运行，但在其他测试用例中失败。知道这种方法有什么问题吗？

标签： c++

解决方案

更好的解决方案，基于 OP 的评论：

#include <string>
#include <iostream>
#include <cctype>

int main() {
    std::string input;
    std::cin >> input;

    unsigned char_xor   = input[ 0 ];
    unsigned pal        = 1; // number of palindromes (initialized to 1, 
                             // since a singular letter is always a 
                             // palindrome)

    for ( std::string::size_type i = 0; input.size() >= i; ++i ) {
        char_xor ^= input[ i + 1 ];

        // check whether length of current prefix is:
        //   - odd: check whether it is a lowercase character
        //   - even: check whether it is equal to 0
        if ( ( i % 2 && std::islower( char_xor ) ) ||
             ( !( i % 2 ) && !char_xor ) ) {
            ++pal;
        }
    }

    std::cout << "Amount of possible palindromes: " << pal << std::endl;

    return 0;
}

以下假设不正确（请参阅下面的评论）。

据了解

如果字符串中所有字符的异或为0，则可以使包含偶数个字符的字符串成为回文。如果字符串具有奇数字符，则所有字符的异或应在97到122之间

您在检查XOR每次迭代（在每个字符之后）计算是否等于 0/97 和 122 之间时犯了一个错误XOR，而您应该在迭代整个std::string. 以下适用于您给定的“abba”示例，例如“aaaadcasdasdaffaaa”（已生成 12 个）：

#include <string>
#include <iostream>
#include <cctype>

bool can_be_palindrome( const std::string& str ) {
    unsigned char_xor = str[ 0 ];

    // compute the xor of all characters
    for ( std::string::size_type i = 1; str.size() != i; ++i ) {
        char_xor ^= str[ i ];
    }

    // determine whether the input string has an even number of characters;
    // if so, return whether char_xor is equal to 0;
    // if not, return whether char_xor is a lowercase letter.
    return !( str.size() % 2 ) ? !char_xor : std::islower( char_xor );
}

int main() {
    std::string input;
    std::cin >> input;

    unsigned pal = 1; // number of palindromes (initialized to 1, since a 
                      // singular letter is always a palindrome)

    for ( std::string::size_type i = 2; input.size() >= i; ++i ) {
        // extract a prefix from the range [0; i) and determine whether it 
        // can become a palindrome
        if ( can_be_palindrome( input.substr( 0, i ) ) ) {
            ++pal;
        }
    }

    std::cout << "Amount of possible palindromes: " << pal << std::endl;

    return 0;
}

推荐阅读