回文字符串问题是常见的算法问题，LeetCode上也有许多回文字符串相关的问题。

回文数字
合法的回文字符串
回文分割
回文分割2

回文数字

Determine whether an integer is a palindrome. Do this without extra space.

click to show spoilers.

Some hints:
Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem “Reverse Integer”, you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem.

这道题和回文字符串没有什么关系，但是好歹也是回文。
实际解题过程中里面还是有一些坑的，负数的数字不算回文，判断的时候要小心溢出。

实际代码比较简单，就是不断判断数字的头部和尾巴是否相同。

bool isPalindrome(int x)
{
    if (x < 0)
        return false;
    int left_factor = 1;
    int right_factor = 1;
    while (x / left_factor >= 10)
    {
        left_factor *= 10;
    }
    while (left_factor >= right_factor)
    {
        if ((x / left_factor) % 10 == (x / right_factor) % 10)
        {
            left_factor /= 10;
            right_factor *= 10;
        }
        else
            break;
    }
    if (left_factor >= right_factor)
        return false;
    else
        return true;
}

合法的回文字符串

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
“A man, a plan, a canal: Panama” is a palindrome.
“race a car” is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

这题也是属于比较简单的，判断一个字符串是否是回文的，要注意题目中提到需要忽略空格和大小写因素。

这里我写的判断比较简单，将原字符串复制进新的字符串，复制的过程中忽略空格并且统一转换成大写，然后直接首尾循环对比就好了。

bool isPalindrome(string s)
{
    int len = s.length();
    if (len <= 1)
        return true;
    string new_str;
    int ignore = 0;
    int start = 0;
    int end;
    for (int i = 0; i < len; i++)
    {
        if (s[i] <= 'z' && s[i] >= 'a' ||
            s[i] <= 'Z' && s[i] >= 'A' ||
            s[i] >= '0' && s[i] <= '9')
        {
            if (s[i] >= 'a')
                new_str.push_back(char(s[i] - 'a' + 'A'));
            else
                new_str.push_back(s[i]);
        }
    }
    int p = 0;
    int q = new_str.length() - 1;
    bool flag = true;
    while (p < q)
    {
        if (new_str[p] != new_str[q])
        {
            flag = false;
            break;
        }
        p++;
        q--;
    }
    return flag;
}

回文分割

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = “aab”,
Return

[
[“aa”,”b”],
[“a”,”a”,”b”]
]

回文分割2

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = “aab”,
Return 1 since the palindrome partitioning [“aa”,”b”] could be produced using 1 cut.