[数据结构与算法]字符串之回文串

本专题主要讲解leetcode上的几道关于回文串的几道简单题，均用C语言编写。

首先，我们介绍下什么是回文串，它是指正读和反读都是一样的字符串，举个例子，例如：“abba”是一个回文串，“abca”则不是。

下面直接看leetcode题，题目如下：

?题目的意思比较简单，就是判断一个字符串是否能够组成回文串。

分析：

回文串的特点：

1. 如果字符串中出现的字符个数全为偶数，则一定可以组成回文子串；

2. 如果字符出现个数为奇数，并且该字符串里面有两个出现奇数的字符，则不可能组成回文串。

实现：

1. 根据上面的分析，首先需要统计字符串中所有字符出现的次数，可以通过一个类似于hash的思想来统计；

2. 只需要判断不符合要求的，返回false即可，其余情况返回true。

具体代码如下：

#define MAX_LEN 10000

bool canPermutePalindrome(char* s){
    int hash[MAX_LEN] = { 0 };
    int len = strlen(s);
    int cnt;
    int i;

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

    for (i = 0; i < MAX_LEN; i++) {
        if (hash[i] % 2 != 0) {
            cnt++;
        }
    }
    if (cnt > 1) {
        return false;
    }
    return true;
}

下面再看第二道题

?首先先理解下题意，题目是要求出构造出最长的回文子串的长度。

分析：

1. 通过上一题的一些回文子串的特点，可以发现，这一道题也能够运用上面的思想，我们可以知道所构造出来的最长的回文子串的长度其实就是字符为偶数的个数加上一个是奇数的字符即可。

实现：

1. 首先还是要统计各字符的个数，如果为奇数，则计数，最后返回字符串长度减去计数的个数加1即可；

2. 需要考虑字符串本身就是回文串的情况，这样直接返回字符串长度即可。

具体代码如下：

#define MAX_NUM 1000

int longestPalindrome(char * s){
    int hash[MAX_NUM] = { 0 };
    int len = strlen(s);
    int cnt = 0;
    int ret = 0;
    int i;

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

    for (i = 0; i < MAX_NUM; i++) {
        if (hash[i] % 2 != 0) {
            cnt++;
        }
    }

    if (cnt == 0) {
        return len;
    }
    ret = len - cnt + 1;
    return ret;
}

接下来看第三道题

这道题是验证字符串是否是回文串，但是有个条件就是可以最多删除一个字符来满足条件

分析：

1.首先需要知道怎么判断字符串是回文串；

2.当左右两个字符不相等的情况，如果字符的下一个或者前一个字符不是回文串，则表示该字符串不满足条件，否则相反

实现：

首先给出两种是否为回文串的实现。具体如下：

bool isPalind(char *s)
{
    int len = strlen(s);
    int i;
    
    for (i = 0; i < len; i++) {
        if (s[i] != s[len - i - 1]) {
            return false;
        }
    }
    return true;
}

bool isPalind(char *s, int left, int right)
{
    while (left < right) {
        if (s[left] != s[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

这道题我们用第二种判断方法，具体代码如下：

bool isPalind(char *s, int left, int right)
{
    while (left < right) {
        if (s[left] != s[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

bool validPalindrome(char * s){
    int len = strlen(s);
    int r = len - 1;
    int l = 0;

    while (l < r) {
        if (s[l] != s[r]) {
            return isPalind(s, l + 1, r) || isPalind(s, l, r - 1);
        }
        l++;
        r--;
    }
    return true;
}

最后，leetcoe的125题也是验证回文串，方法差不多，这里就不再赘述。