关于回文问题

回文问题的解法：双指针，栈，reverse

1. 409. 最长回文串[✔]

2. 125. 验证回文串[✔]

3. 5. 最长回文子串（返回子串）[✔]

4.NC17最长回文子串（返回子串长度）研发最爱考[✔]

5. 516. 最长回文子序列[✔]

6.NC96判断一个链表是否为回文结构研发最爱考[✔]

1. 409. 最长回文串[✔]

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

思路：HashSet

将字符串转换为字符数组，遍历该数组，判断对应字符是否在HashSet中，如果不在，则加入；如果在，就让count++并移除该字符。这样能够找到出现次数为双数的字符个数。构成回文串有两种情况：字符出现次数为双数的组合和字符出现次数为双数的组合+一个只出现一次的字符。类似于打牌。

class Solution {
    public int longestPalindrome(String s) {
        if(s.length() == 0) return 0;
        HashSet<Character> set = new HashSet<>();
        char[] chs = s.toCharArray();
        int count = 0;
        for(int i = 0; i < chs.length; i++){
            if(!set.contains(chs[i])){
                set.add(chs[i]);
            }else{
                set.remove(chs[i]);
                count++;
            }
        }
    return set.isEmpty() ? count * 2 : count * 2 + 1;
    }
}

2. 125. 验证回文串[✔]

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

思路：双指针

使用双指针，一个指向前，一个指向后，从头和尾开始向中间遍历，遇到空格以及特殊字符要跳过，然后判断。

class Solution {
    public boolean isPalindrome(String s) {
        if (s == null || s.length() == 0)
            return true;
        s = s.toLowerCase();
        int i = 0;
        int j = s.length() - 1;
        while(i < j){
            if(!Character.isLetterOrDigit(s.charAt(i))){
                i++;
                continue;
            }
            if(!Character.isLetterOrDigit(s.charAt(j))){
                j--;
                continue;
            }
            if (s.charAt(i) != s.charAt(j)){
                return false;
            }
            i++;
            j--;
        }
        return true;
    }

}

3. 5. 最长回文子串

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

思路一：动态规划

class Solution {
    public String longestPalindrome(String s) {//执行用时 :138 ms, 在所有 Java 提交中击败了33.51%的用户
        int len = s.length();
        if(len < 2)
            return s;//此时一定是回文串
        boolean[][] dp = new boolean[len][len];//定义状态dp[i][j]表示子串s[i, j]是否为回文子串
        for(int i=0;i<len;i++){
            dp[i][i] = true;//初始化，单个字符一定是回文串
        }
        int maxLen = 1;
        int start = 0;
        for(int i=len-2;i>=0;i--){//i要降序（因为dp[i][j] = dp[i+1][j-1]）
            for(int j=i+1;j<len;j++){//j要升序（因为dp[i][j] = dp[i+1][j-1]）
                if(s.charAt(i) == s.charAt(j)){
                    if(j-i<3){//(j-1)-(i+1)+1<2，即为[i+1, j-1]不构成区间，边界条件，dp值可以直接判断
                        dp[i][j] = true;
                    }else{
                        dp[i][j] = dp[i+1][j-1];//状态转移方程
                    }
                }else{
                    dp[i][j] = false;
                }
                if(dp[i][j]){//子串s[i, j]是回文子串时，记录长度和起始位置
                    int currentLen = j-i+1;
                    if(currentLen > maxLen){
                        maxLen = currentLen;
                        start = i;
                    }
                }
            }
        }   
    return s.substring(start, start+maxLen);//最长的回文子串
    }
}

思路二：中心扩散法

class Solution {
    int index = 0;
    int len = 0;
    public String longestPalindrome(String s) {
        if(s.length() < 2)  return s;
        for(int i = 0; i < s.length(); i++){
            // left = right 的时候，此时回文中心是一个字符，回文串的长度是奇数
            // right = left + 1 的时候，此时回文中心是一个空隙，回文串的长度是偶数
            PalindromeHeper(s, i, i);
            PalindromeHeper(s, i, i + 1);
        }
    return s.substring(index, index + len);
    }

    public void PalindromeHeper(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;
        }
    }
}

4.NC17最长回文子串研发最爱考[✔]

题目描述:
对于一个字符串，请设计一个高效算法，计算其中最长回文子串的长度。
给定字符串A以及它的长度n，请返回最长回文子串的长度。
测试样例：
"abc1234321ab",12
返回：7

思路：动态规划

1.定义状态：dp[i][j]表示子串A[ i , j ] 是否为回文串
2.考虑状态转移方程：
如果s[i] == s[j] ，那么dp[i][j] = false;
如果s[i] == s[j] ，那么分两种情况
(1)表达式 [i + 1, j - 1] 不构成区间，即长度严格小于 2，即 j - i < 3时，dp[i][j] = true
(2)表达式 [i + 1, j - 1] 可以构成区间，dp[i][j] = dp[i + 1][j - 1]
3.考虑初始化：单个字符一定是回文串，因此把对角线先初始化为 true，即 dp[i][i] = true
4.考虑输出：求的是最长回文子串的长度，因此当dp[i][i] = true时，就更新子串的长度
注意填表顺序，要想求得dp[i][j]要先知道dp[i + 1][j - 1]即为左下角的值，我想到的填表顺序是题解中的这种。

import java.util.*;

public class Palindrome {
    public int getLongestPalindrome(String A, int n) {
        // write code here
        if(n < 2)    return n;
        //int len = 0;
        int max = 1;
        boolean[][] dp = new boolean[n][n];
        for(int i = 0; i < n; i++){
            dp[i][i] = true;
        }
        
        for(int i = n - 2; i >= 0; i--){
            for(int j = i + 1; j < n; j++){
                char[] c = A.toCharArray();
                if(c[i] != c[j]){
                    dp[i][j] = false;
                }else{
                    if(j - i < 3){
                        dp[i][j] = true;
                    }else{
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                if(dp[i][j] && j - i + 1 > max){
                    max = j - i + 1;
                }
            }
        }
        return max;
    }
}

5. 516. 最长回文子序列

给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。
示例 1:
输入:"bbbab"
输出:4，一个可能的最长回文子序列为 "bbbb"。
提示：

• 1 <= s.length <= 1000
• s 只包含小写英文字母

思路：动态规划

图片来自https://leetcode-cn.com/problems/longest-palindromic-subsequence/solution/zi-xu-lie-wen-ti-tong-yong-si-lu-zui-chang-hui-wen/

已知子问题 dp[i+1][j-1] 的结果（s[i+1..j-1] 中最长回文子序列的长度）
如果s[i] = s[j]，那么它俩加上 s[i+1..j-1] 中的最长回文子序列就是 s[i..j] 的最长回文子序列：
如果s[i] != s[j]，说明它俩不可能同时出现在 s[i..j] 的最长回文子序列中，那么把它俩分别加入 s[i+1..j-1] 中，看看哪个子串产生的回文子序列更长即可：

class Solution {
    public int longestPalindromeSubseq(String s) {
        int len = s.length();
        int [][] dp = new int[len][len];
        for(int i = 0 ; i < len; i++){
            dp[i][i] = 1;
        }
        for(int i = len - 2; i >= 0; i--){
            for(int j = i + 1; j < len; j++){
                if(s.charAt(i) == s.charAt(j)){
                     dp[i][j] = dp[i + 1][j - 1] + 2;
                }     
                else{
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }    
            }
        }
    return dp[0][len - 1];
    }
}

6.NC96判断一个链表是否为回文结构研发最爱考[✔]

与 234. 回文链表相同[✔]

题目描述：
给定一个链表，请判断该链表是否为回文结构。
示例1：
输入：[1,2,2,1]，输出：true
备注：1≤n≤10⁶
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题吗？

思路:

找到前半部分链表的尾节点，反转后半部分链表，判断是否为回文，恢复链表，返回结果
反转链表有两种方法：双指针迭代和递归
206. 反转链表
双指针迭代比较容易想到：
申请两个指针，第一个指针叫 pre，最初是指向 null 的。
第二个指针 cur 指向 head，然后不断遍历 cur。
每次迭代到 cur，都将 cur 的 next 指向 pre，然后 pre 和 cur 前进一位。
都迭代完了(cur 变成 null 了)，pre 就是最后一个节点了。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {//执行用时：1 ms, 在所有 Java 提交中击败了99.70%的用户，2020/08/04
    public boolean isPalindrome(ListNode head) {
        if(head == null)    return true;
        ListNode firstHalfEnd = findMid(head);//找到前半部分链表的尾节点
        ListNode secondHalfStart = reverse(firstHalfEnd.next);//反转后半部分链表
        ListNode p1 = head;
        ListNode p2 = secondHalfStart;
        boolean res = true;
        while(res && p2 != null){
            if(p1.val != p2.val){
                res = false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        firstHalfEnd.next = reverse(secondHalfStart);//恢复链表
        return res;
    }
    //使用快慢指针找到前半部分链表的尾节点
    //如果要求「在两个中间结点的时候，返回第一个中间结点]
    //此时快指针可以前进的条件是：当前快指针的下一个结点和当前快指针的下下一个结点都非空
    private ListNode findMid(ListNode head){
        ListNode fast = head;
        ListNode slow = head;
        //while(fast != null && fast.next != null){
        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
        
    }
    //反转链表：双指针迭代
    private ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null){
            ListNode tmpNext = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmpNext;
        }
        return pre;
    }

}