04.回文字符串

目录介绍

01.题目要求
02.最长回文串
03.验证回文串
04.最长回文子串

01.题目要求

问题如下所示：
- 回文串：“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。

示例 :

1234321    level    noon 等都是回文字符串

02.最长回文串

给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。在构造过程中，请注意区分大小写。比如"Aa"不能当做一个回文字符串。注意:假设字符串的长度不会超过 1010。示例 1:
```
输入:
"abccccdd"

输出:
7

解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
```
可以构成回文串的两种情况：
- 字符出现次数为双数的组合
- 字符出现次数为双数的组合+一个只出现一次的字符

代码实现

统计字符出现的次数即可，双数才能构成回文。因为允许中间一个数单独出现，比如“abcba”，所以如果最后有字母落单，总长度可以加 1。首先将字符串转变为字符数组。然后遍历该数组，判断对应字符是否在hashset中，如果不在就加进去，如果在就让count++，然后移除该字符！这样就能找到出现次数为双数的字符个数。

public  int LengthPalindrome(String s) {
    if (s.length() == 0){
        return 0;
    }
    // 用于存放字符
    HashSet<Character> hashSet = new HashSet<>();
    char[] chars = s.toCharArray();
    int count = 0;
    for (int i = 0; i < chars.length; i++) {
        // 如果hashSet没有该字符就保存进去
        if (!hashSet.contains(chars[i])) {
            hashSet.add(chars[i]);
        } else {
            // 如果有,就让count++（说明找到了一个成对的字符），然后把该字符移除
            hashSet.remove(chars[i]);
            count++;
        }
    }
    return hashSet.isEmpty() ? count * 2 : count * 2 + 1;
}

03.验证回文串

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。说明：本题中，我们将空字符串定义为有效的回文串。
- 示例 1:
```
输入: "A man, a plan, a canal: Panama"
输出: true
```
- 示例 2:
```
输入: "race a car"
输出: false
```

代码如下所示

public  boolean IsPalindrome(String s) {
    if (s.length() == 0){
        return true;
    }
    int l = 0, r = s.length() - 1;
    while (l < r) {
        // 从头和尾开始向中间遍历
        // 字符不是字母和数字的情况
        if (!Character.isLetterOrDigit(s.charAt(l))) {
            l++;
        } else if (!Character.isLetterOrDigit(s.charAt(r))) {
            // 字符不是字母和数字的情况
            r--;
        } else {
            // 判断二者是否相等
            if (Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r)))
                return false;
            l++;
            r--;
        }
    }
    return true;
}

04.最长回文子串

最长回文子串给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。
- 示例 1：
```
输入: "babad"
输出: "bab"
注意: "aba"也是一个有效答案。
```
- 示例 2：
```
输入: "cbbd"
输出: "bb"
```

代码如下所示

private int index, len;
public String LongestPalindrome(String s) {
    if (s.length() < 2){
        return s;
    }
    for (int i = 0; i < s.length() - 1; i++) {
        PalindromeHelper(s, i, i);
        PalindromeHelper(s, i, i + 1);
    }
    return s.substring(index, index + len);
}

public void PalindromeHelper(String s, int l, int r) {
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
        l--;
        r++;
    }
    if (len < r - l - 1) {
        index = l + 1;
        len = r - l - 1;
    }
}