对于一个字符串添加一个字符是否可以构成回文字符串

对于一个字符串对其添加一个字符可以构成回文字符串吗

---

方法一：逆思维思考

对于添加一个字符可以构成回文字符串的话，那么删除一个字符也就可以构成回文字符串了，所以就可以对于这个字符串的每一个字符进行删除，然后在判断是不是回文字符串，如果是的话，那就可以，否则不可以

代码实现：

#include <iostream>
#include <string>
​
//判断一个字符串是不是回文字符串
bool Check(const std::string& str)
{
    int len = str.size();
    for (size_t i = 0; i < len / 2; i++)
    {
        if (str[i] != str[len - i - 1])
        {
            return false;
        }
    }
​
    return true;
}
​
int main()
{
    std::string str;
    //char str1[1000];
    //std::cin >> str1;
    //str = str1;
    bool flag;
    while (std::cin >> str)
    {
        for (size_t i = 0; i < str.size(); i++)
        {
            std::string tmpStr = str;
            for (size_t j = i; j < str.size(); j++)
            {
                tmpStr[j] = tmpStr[j + 1];
            }
            tmpStr.resize(str.size() - 1);
            if (flag = Check(tmpStr))
            {
                std::cout << "YES" << std::endl;
                break;
            }
        }
        if (!flag)
        std::cout << "NO" << std::endl;
    }
    return 0;
}

方法二：对于方法一进行改进
设置i和j，分别是最左边和最右边下标，每次比较左右两边相同位置的字符，相同的话就继续比较。设置一个x表示的是删除字符串限制，x=2表明最多可以删除一个字符

否则的话将i++之后和j继续比较，或者j--之后和i继续比较（此时x--），如果可以一直比完的话，那就是回文的字符串，也就相当于删除一个字符串。

如果都不可以话，那就说明删除一个字符无法变成回文字符串（x--），需要删除至少两个才可以构成回文字符串

最后只需要判断x就可以知道是否可以构成回文字符串

代码实现：

std:string str;
while (cin >> str) 
{
    int i, l = str.length(), x = 2, j = l - 1;
    for (i = 0; i<j; i++, j--) 
    {
        if (str[i] != str[j]) 
        {
            x--;
            if (str[i + 1] == str[j])
                i++;
            else if (str[i] == str[j - 1])
                j--;
            else
                x--;
        }
    }
    if (x>0)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}

方法三：

也是设置一个i和j指针，分别从两变相同的位置向中间比较，直到不相同位置。

此时如果要添加一个字符构成回文字符串的话，那就是将左边的添加到右边，或者将最后边的添加到左边

再次对添加之后的字符串进行判断是不是回文字符串，如果是的话可以，否则失败

代码实现：

//判断是否是回文串，是的话返回-1,不是的话对应位置返回下标
//因为失败要返回下标，所以满足条件并没有采取返回非负值而是-1
int IsPalindromeString(string str)
{
    //对比对应位置字符是否相同
    int len = str.size();
    for (int i = 0; i < len / 2; ++i)
    {
        if (str[i] != str[len - i - 1])
            return i;
    }
    return -1;
}
​
bool InsertCharIsParlindromString(string str)
{
    int size = str.size();
    int pos = IsPalindromeString(str);
    //本身不是回文串
    if (pos != -1)
    {
        //代码思想：从不一致的位置开始，取到右边与它对应位置的子串
        //在子串前面加子串的末尾值，或者在子串末尾加子串的最前值
        //原因如下，符合条件的话会满足其中一个
        //如果是左边缺，则子串末尾的值就是左边缺的，添回就是回文串
        //如果是右边缺，则子串开始的值就是右边缺的，添回就是回文串
​
        //右边与pos对应的位置的值 加上 pos开始，长度size-2*pos的子串
        //给左边加上右边的值
        int result1 = IsPalindromeString(str[size - 1 - pos] + str.substr(pos, size - 2 * pos));
        //pos开始，长度size-2*pos的子串 加上 pos位置的值
        //给右边加上左边的值
        int result2 = IsPalindromeString(str.substr(pos, size - 2 * pos) + str[pos]);
        if ((result1 == -1) || (result2 == -1))
            return true;
        else
            return false;
    }
    //本身是回文串,添加指定字符还是回文串
    else
    {
        return true;
    }
}
​
​
int main()
{
    string str;
    while (cin >> str)
    {
        bool result = InsertCharIsParlindromString(str);
        if (result == true)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

插图：