c - 在 C 中重新排列字符串以形成回文

Question

给定 C 中的字符串。

如何重新排列给定的字符串以使其形成回文？

有没有办法在O(n)时间复杂度和O(1)空间复杂度上实现它？

标签： cstringpalindrome

Answer 1

bool canFormPalindrome(string str)
{
    // Create a count array and initialize all
    // values as 0
    int count[NO_OF_CHARS] = { 0 };
 
    // For each character in input strings,
    // increment count in the corresponding
    // count array
    for (int i = 0; str[i]; i++)
        count[str[i]]++;
 
    // Count odd occurring characters
    int odd = 0;
    for (int i = 0; i < NO_OF_CHARS; i++) {
        if (count[i] & 1)
            odd++;
 
        if (odd > 1)
            return false;
    }
 
    // Return true if odd count is 0 or 1,
    return true;
}