前言

美好的一天从hard结束。。。

原文链接：《算法零基础100讲》(第26讲) 字符串算法(六) - 回文串

面试题 01.04. 回文排列

原题链接：面试题 01.04. 回文排列

代码

将问题转化为判断同一字符是否为奇数 的字符个数，如果超过两个，就返回错误。

bool canPermutePalindrome(char* s)
{
    if (NULL == s)
        return NULL;

    int hash[SIZE];
    memset (hash, 0, sizeof(hash));

    for (int i = 0; i < strlen(s); ++i)
    {
        ++hash[s[i]];
    }

    int count = 0;

    for (int i = 0; i < SIZE; ++i)
    {
        if (hash[i] % 2 == 1)
        {
            ++count;
        }
        if (count >= 2)
        {
            return false;
        }
    }

    return true;
}

剑指 Offer II 018. 有效的回文

原题链接：剑指 Offer II 018. 有效的回文

代码

//判断非字符和数字
bool Unqualified(char c)
{
    return (!isalpha(c) && !isdigit(c));
}

//大写字母
bool Isbig(char c)
{
    return (c >= 'A' && c <= 'Z');
}

bool isPalindrome(char * s)
{
    if (NULL == s)
        return true;
    
    int left = 0, right = strlen(s) - 1;

    while (left <= right)
    {
        while (left <= right && Unqualified(s[left]))
        {
            ++left;
        }
        while (left <= right && Unqualified(s[right]))
        {
            --right;
        }

        if (left <= right)
        {
            if (Isbig(s[left]))
                s[left] += 32;
            if (Isbig(s[right]))
                s[right] += 32;

            if (s[left] != s[right])
            {
                return false;
            }
        }

        ++left;
        --right;
    }    
    
    return true;
}

125. 验证回文串

原题链接：125. 验证回文串

代码

和上个题一样，不过代码可以随便写

char Change(char ch)
{
    if (ch >= 'a' && ch <= 'z')
    {
        ch -= 32;
    }
    return ch;
}

bool isPalindrome(char * s)
{
    if (s == NULL) return false;

    int len = strlen(s);
    int ans[len];
    memset(ans, 0, sizeof(char) * len);

    int n = 0;
    //把字母和数字写进去
    for (int i = 0; i < len; ++i)
    {
        if (isalnum(s[i]))
        {
            s[i] = Change(s[i]);
            ans[n++] = s[i];
        }
    }
  
    char* p = ans, *q = ans + n - 1;

    for (; p <= q;)
    {
        if (*p != *q)
        {
            return false;
        }
        p++;
        q--;
    }

    return true;
}

409. 最长回文串

原题链接：409. 最长回文串

代码

对于字符是偶数个数的，直接加到答案长度中；对于奇数，加上数字减一；最后的加一是奇数的一。

#define SIZE 256

int longestPalindrome(char * s)
{
    if (NULL == s) return -1;

    int hash[SIZE];
    memset(hash, 0, sizeof(hash));

    for (int i = 0; i < strlen(s); ++i)
    {
        ++hash[s[i] - 'A'];
    }

    int length = 0;

    for (int i = 0; i < SIZE; ++i)
    {
        length += hash[i] - hash[i] % 2;
    }

    return length + (length != strlen(s));
}

剑指 Offer II 019. 最多删除一个字符得到回文

680. 验证回文字符串 Ⅱ

原题链接：剑指 Offer II 019. 最多删除一个字符得到回文

原题链接：680. 验证回文字符串 Ⅱ

代码

bool solution(char* s, int left, int right, int flag)
{
    if (left >= right)
        return true;

    if (s[left] == s[right])
        return solution(s, left+1, right-1, flag);

    if (flag) 
        return false;
    else
        return (solution(s, left + 1, right, 1) || solution(s, left, right - 1, 1));
}

bool validPalindrome(char* s)
{
    if (NULL == s)
        return true;
    
    return solution(s, 0, strlen(s) - 1, 0);
}

1332. 删除回文子序列

原题链接：1332. 删除回文子序列

代码

int removePalindromeSub(char * s)
{
    int len = strlen(s);

    if (NULL == s || len == 0)
        return 0;
    
    int left = 0, right = len - 1;
    while (left < right)
    {
        if (s[left++] != s[right--])
        {
            return 2;
        }
    }

    return 1;
}

练习题

美好的一天直接结束

214. 最短回文串
     原题链接：214. 最短回文串