回文字符串（验证/最长/最短/分割）

1.验证回文串（125-易）

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。ps：我们将空字符串定义为有效的回文串。

示例 :

输入: "A man, a plan, a canal: Panama"
输出: true

思路分析：

法1：比较常规的做法就是使用双指针，这里注意忽略字母的大小写，即 A == a ，对于其他非法字符直接跳过，但只考虑字母和数字字符。

法2：这里分享另一个 思路 。将字符建立映射关系，具体是把 '0' 到 '9' 映射到 1 到 10，'a' 到 'z' 映射到 11 到 36 ，'A' 到 'Z' 也映射到 11 到 36 。然后把所有数字和字母用一个 char 数组存起来，没存的字符就默认映射到 0 了。

这样只需要判断字符串中每个字母映射过去的数字是否相等，如果是acsii值为 0， 就意味着它是非法字符，对应映射位置为空。

代码实现:

// 双指针
public boolean isPalindrome(String s) {
    s = s.toLowerCase();
    if (s == null && s.length() == 0) {
        return true;
    }
    int l = 0, r = s.length() - 1;
    char[] cs = s.toCharArray();

    while (l < r) {
        // 剔除非法字符（即找到有效的对比）
        while (!isAlphanumeric(cs[l]) && l < r) l++;
        while (!isAlphanumeric(cs[r]) && l < r) r--;
        
        if (cs[l] != cs[r]) {
            return false;
        }
        l++;
        r--;
    }
    return true;
}

// 合法字符：字母和数字
private boolean isAlphanumeric(char c) {
    if (c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z' || c >= '0' && c <= '9') {
        return true;
    }
    return false;
}

// 解法2：映射+双指针
private char[] charMap = new char[256];

public boolean isPalindrome(String s) {
    
    // 建立映射('1~10', '11~36')
    for (int i = 0; i < 10; i++) {
        charMap[i + '0'] = (char) (1 + i);
    }
    for (int i = 0; i < 26; i++) {
        charMap[i + 'A'] = charMap[i + 'a'] = (char) (11 + i);
    }

    char[] cs = s.toCharArray();
    int l = 0, r = cs.length - 1;
    char sl, sr;
    while (l < r) {
        sl = charMap[cs[l]];
        sr = charMap[cs[r]];
        // 检查映射是否为空
        if (sl != 0 && sr != 0) {
            if (sl != sr) {
                return false;
            }
            l++;
            r--;
        } else {
            if (sl == 0) {
                l++;
            } else {
                r--;
            }
        }
    }
    return true;
}

2.验证回文串ii（680-易）

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

示例:

输入: "abca"
输出: True
解释: 你可以删除c字符。

思路分析：基于双指针实现，最多删除一个元素，也可以不做删除操作。那么我们就对删除一个元素进行分析，即出现某次不对称时，删除一个元素，继续进行比较，这里我们通过调用isPalindrome函数判断字符串区间是否回文。

代码实现：

class Solution {
    public boolean validPalindrome(String s) {
        char[] cs = s.toCharArray();
        int i = 0, j = cs.length - 1;

        while (i < j && cs[i] == cs[j]) {
            i++;
            j--;
        }
        if (isPalindrome(cs, i, j - 1)) {
            return true;
        }
        if (isPalindrome(cs, i + 1, j)) {
            return true;
        }
        return false;
        
    }

    public boolean isPalindrome(char[] cs, int i, int j) {
        while (i < j) {
            if (cs[i] != cs[j]) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}

3.最短回文串(214-难)

题目描述：给定一个字符串 s，你可以通过在字符串前面添加字符（即添加前缀）将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。

示例 :

输入: "abcd"
输出: "dcbabcd"

思路分析：本题可以用双指针实现，但这里用字符串匹配感觉比较合适。本案例关键就是求出从开头开始(前缀)的最长回文串!!!参考这里

思路1：对原字符串进行反转匹配，举例：

abbacd

原s: abbacd, 长度记为 n
逆r: dcabba, 长度记为 n

判断 s[0,n) 和 r[0,n)
abbacd != dcabba

判断 s[0,n - 1) 和 r[1,n)
abbac != cabba  

判断 s[0,n - 2) 和 r[2,n)
abba == abba  

从开头开始的最长回文串也就找到了, 接下来只需要将末尾不是回文串的部分倒置加到原字符串开头即可，但过于暴力！

思路2：对思路1字符串匹配进行优化，我们知道字符串匹配算法还有KMP算法。

如果我们把思路1中的例子 abbacd dcabba看成一个字符串，中间加上一个分隔符 #（避免计算公共前后缀出错），abbacd#dcabba。

左右部分可以对应拼接字符串的前缀和后缀，即寻找前缀和后缀相等的子串。我们如果求出了 abbacd#dcabba 的 next 数组，因为我们构造的字符串后缀就是原字符串的倒置，前缀后缀相等时，也就意味着当前前缀是一个回文串，而 next 数组是寻求最长的前缀，我们也就找到了开头开始的最长回文串。

思路3：马拉车算法，待补充...

代码实现：

解法1：反转字符串

public String shortestPalindrome(String s) {
    String r = new StringBuilder(s).reverse().toString();
    int n = s.length();
    int i = 0;
    for (; i < n; i++) {
        if (s.substring(0, n - i).equals(r.substring(i))) {
            break;
        } 
    }
    return r.substring(0, i) + s;
}

解法2：KMP

public String shortestPalindrome(String s) {
    String ss = s + "#" + new StringBuilder(s).reverse();
    int max = getLastNext(ss);
    return new StringBuilder(s.substring(max)).reverse() + s;
}
// 获取next数组（即当前位置之前存放的最大匹配长度）的最后一个值
private int getLastNext(String s) {
    int n = s.length();
    char[] chs = s.toCharArray();
    int[] next = new int[n + 1];
    // 初始化
    next[0] = -1;
    next[1] = 0;
    int k = 0; // 最大匹配(前后缀相等)长度
    int i = 2; // 当前最后一个位置

    while (i <= n) {
        if (k == -1 || chs[i - 1] == chs[k]) {
            next[i] = k + 1;
            k++;
            i++;
        } else {
            k = next[k];
        }
    }
    return next[n];
}

4.构造最长的回文串（409-易）

给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。

示例 :

输入:"abccccdd"
输出:7
解释:我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

思路分析：

法1：本题要求通过输入构造最长回文串的长度，故可以统计每次字符出现的次数，最后考虑奇数情况完成字符串构造。

法2：这里可以对数组长度和统计方法进行优化，这里只需要统计偶数（奇数 - 1）出现的个数，见解法2，参考这里：）

代码实现：

class Solution {

    // 统计每个字符出现的次数
    public int longestPalindrome(String s) {
        int[] cnts = new int[256];
        char[] cs = s.toCharArray();

        for (char c : cs) {
            cnts[c]++;
        }
        int len = 0;
        for (int cnt : cnts) {
            // 只考虑偶数部分
            len += (cnt / 2) * 2;
        }
        if (len < s.length()) {
            len++;
        }
        return len;
    }

    // 优化（题意优化空间和统计逻辑）
    public int longestPalindrome(String s) {
        int[] cnts = new int[58];
        char[] cs = s.toCharArray();

        for (char c : cs) {
            cnts[c - 'A']++;
        }
        int len = 0;
        for (int cnt : cnts) {
            len += cnt - (cnt & 1);
        }
        return len < s.length() ? len + 1 : len;
    }
}

ps：这里为什么申请58个位置，不应该是52吗？这里你要看一下ASCII码表，可以参考这里，大写字母ASCII值从64-90；小写字母的ASCII值从97-122，中间间隔6个字符，so。

5.回文子串（647-中）

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。

示例:

输入: "aaa"
输出: 6
说明: 6个回文子串: "a", "a", "a", "aa", "aa", "aaa".

思路分析：遍历字符串中的每个字符，尝试从字符串的每个位置进行字符串扩展，向左右两边扩展每个位置（即定义两个变量更新左右边界），并统计回文子串的数量。ps：但这里要注意奇偶，即每次固定字符个数，两种扩展情况！

示例：
z x x c
注：扩展时固定一个字符有4个，固定两个字符有2个，共6个
a b a
注：扩展时固定一个字符有4个，固定两个字符有0个，共4个

代码实现：

class Solution {

    private int count = 0;
    public int countSubstrings(String s) {
        char[] cs = s.toCharArray();
        int n = cs.length;

        for (int i = 0; i < n; i++) {
            extendSubString(cs, i, i);
            extendSubString(cs, i, i + 1);
        }
        return count;
    }

    // 向两侧扩展字符串
    private void extendSubString(char[] cs, int left, int right) {
        while (left >= 0 && right < cs.length && cs[left] == cs[right]) {
            left--;
            right++;
            count++;
        }
    }
}

6.最长的回文子串（5-中）

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 ：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

思路分析：

思路1：和上题中回文子串思路相同，遍历字符串，从不同位置开始扩展字符串（获取扩展子串的长度），但要注意奇偶两种情况！定义两个变量 start 和 end ，当最大长度发生变化进行更新这两个边界。

思路2：动态规划，同时也需要更新当前最大回文串的长度和左右边界。

• dp[i][j] 表示 s[i, j] 是否是回文串
• 状态转移方程：cs[i] == cs[j] 并且 区间[i + 1, j - 1]是回文串或者只剩下i，j两个元素，区间[i, j]是一定是回文串，否则不是。

思路3：马拉车算法，待补充...

代码实现：

class Solution {
    
    // 中心扩展法 
    public String longestPalindrome(String s) {
        char[] cs = s.toCharArray();
        int len = cs.length;
        if (len < 2) {
            return s;
        }

        int start = 0;
        int end = 0;
        for (int i = 0; i < len; i++) {
            int len1 = extendSubString(cs, i, i);
            int len2 = extendSubString(cs, i, i + 1);

            int max = Math.max(len1, len2);
            if (max > end - start) {
                // 对于（如a b b a），i代表左b位置
                start = i - (max - 1) / 2;
                end = i + max / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    private int extendSubString(char[] cs, int left, int right) {
        while (left >= 0 && right < cs.length && cs[left] == cs[right]) {
            left--;
            right++;
        }
        return right - left - 1;
    }

    // 动态规划
    public String longestPalindrome(String s) {
        char[] cs = s.toCharArray();
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        int start = 0;
        int end = 0;
        int maxLen = 0;

        for (int j = 0; j < len; j++) {
            for (int i = 0; i < j; i++) {
                if (cs[i] == cs[j] && (dp[i + 1][j - 1] || j - i < 3)) {
                    dp[i][j] = true;
                    if (j - i + 1 > maxLen) {
                        maxLen = j - i + 1;
                        start = i;
                        end = j;
                    }
                }
            }
        }
        return s.substring(start, end + 1);
    }
}

7.最长回文子序列（516-中）

给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。

子序列，指某个序列的子序列是从最初序列通过去除某些元素但不破坏余下元素的相对位置（在前或在后）而形成的新序列。

示例 :

输入:"bbbab"
输出:4
注：一个可能的最长回文子序列为 "bbbb"。

思路分析：注意：一旦涉及到子序列/最值，那几乎可以肯定，考察的是动态规划技巧，时间复杂度一般都是 O(n^2)。

• dp 数组的定义是：在子串 s[i..j] 中，最长回文子序列的长度为 dp[i][j]。一般求什么设什么。
• 状态转移方程：如果我们想求dp[i][j]，假设你知道了子问题 dp[i + 1][j - 1] 的结果（s[i+1..j-1] 中最长回文子序列的长度），可以算出 dp[i][j]的值（s[i..j] 中，最长回文子序列的长度），

关键：我们只需要判断新加入的两个元素的大小，若相等加入，若不相等，即不能同时加入，我们需要取两个元素加入的最大值即可。

if (s[i] == s[j])
    // 它俩一定在最长回文子序列中
    dp[i][j] = dp[i + 1][j - 1] + 2;
else
    // s[i+1..j] 和 s[i..j-1] 谁的回文子序列更长？
    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

动态规划流程：

• base case：只有一个元素，显然最长回文子序列长度是 1，也就是 dp[i][j] = 1 (i == j)；
• 当i > j 时， 不存在最长子序列，即长度初始化0；
• 上述代码和图示已经确定一个基本位置的依赖关系，目标位置dp[0][n - 1]
• 为了保证每次计算 dp[i][j]，左下右方向的位置已经被计算出来，只能斜着遍历或者反着遍历

代码实现：

class Solution {
    
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        char[] cs = s.toCharArray();
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; ++i) {
            dp[i][i] = 1;
        }

        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (cs[i] == cs[j]) {
                    // 相等直接加入
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
                }
            }
        }
        return dp[0][n - 1];
    }
}

8.分割回文串（131-中）

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。

举例：

输入: "aab"
输出:
[
  ["aa","b"],
  ["a","a","b"]
]

思路分析：

法1：暴力递归：将大问题分解为小问题（回文串），利用小问题的结果解决当前大问题。上述案例分析:

输入：aab
    
先考虑在第 1 个位置切割，a | ab
这样我们只需要知道 ab 的所有结果，然后在所有结果的头部把 a 加入
ab 的所有结果就是 [a b]
每个结果头部加入 a，就是 [a a b]

再考虑在第 2 个位置切割，aa | b
这样我们只需要知道 b 的所有结果，然后在所有结果的头部把 aa 加入
b 的所有结果就是 [b]
每个结果头部加入 aa,就是 [aa b]

再考虑在第 3 个位置切割，aab |
因为 aab 不是回文串，所有直接跳过

最后所有的结果就是所有的加起来
[a a b] [aa b]

法2：动态规划：每次判断一个字符串是否是回文串的时候，我们都会调用 isPalindrome 判断。这就会造成一个问题，比如字符串 abbbba，期间我们肯定会判断 bbbb 是不是回文串，也会判断 abbbba 是不是回文串。判断 abbbba 是不是回文串的时候，在 isPalindrome 中依旧会判断中间的 bbbb 部分。而其实如果我们已经知道了 bbbb 是回文串，只需要判断 abbbba 的开头和末尾字符是否相等即可。

所以我们为了避免一些重复判断，可以用动态规划的方法，把所有字符是否是回文串提前存起来，空间换时间的思想。

对于字符串 s。用 dp[i][j] 表示 s[i，j] 是否是回文串，然后有状态转移方程 dp[i][j] = s[i] == s[j] && dp[i+1][j-1] 。我们只需要两层 for 循环，从每个下标开始，考虑所有长度的子串即可。

因为要保证 dp[i + 1][j - 1] 中 i + 1 <= j - 1：

i + 1 <= j - 1
j = i + len - 1 
化简得
len >= 3

所以为了保证正确，多加了 len < 3 的条件。也就意味着长度是 1 和 2 的时候，我们只需要判断 s[i] == s[j]。然后把 dp 传入到递归函数中即可。

法3：回溯算法：根据动态确定每个下标和长度的字符串是否为回文串。满足条件的话，依次进行更新：选择，递归，撤销选择。可以传入回溯算法作为参数，套用回溯算法模板。

代码实现：

public List<List<String>> partition(String s) {
    return partitionHelper(s, 0);
}

private List<List<String>> partitionHelper(String s, int start) {
    // 递归出口：分割位置start == s.length()
    if (start == s.length()) {
        List<List<String>> ans = new ArrayList<>();
        List<String> list = new ArrayList<>();
        ans.add(list);
        return ans; 
    }
    
    List<List<String>> ans = new ArrayList<>();
    for (int i = start; i < s.length(); i++) {
        if (isPalindrome(s.substring(start, i + 1))) {
            String left = s.substring(start, i + 1);
            for (List<String> l : partitionHelper(s, i + 1)) {
                // 每个结果头部加上回文子串left
                l.add(0, left);
                ans.add(l);
            }
        }
    }
    return ans;
}

private boolean isPalindrome(String s) {
    int i = 0, j = s.length() - 1;
    while (i < j) {
        if (s.charAt(i++) != s.charAt(j--)) return false;
    }
    return true;
}

解法2：动态规划（空间换时间）

public List<List<String>> partition(String s) {
    int n = s.length();
    boolean[][] dp = new boolean[n][n];
    char[] ch = s.toCharArray(); 
    for (int len = 1; len <= n; len++) {   //所有长度
        for (int i = 0; i <= n - len; i++) {  //每个下标
            int j = i + len - 1;
            dp[i][j] = ch[i] == ch[j] && (len < 3 || dp[i + 1][j - 1]);
        }
    }
    return partitionHelper(s, 0, dp);
}

private List<List<String>> partitionHelper(String s, int start, boolean[][] dp) {
    if (start == s.length()) {
        List<String> list = new ArrayList<>();
        List<List<String>> ans = new ArrayList<>();
        ans.add(list);
        return ans; 
    }
    List<List<String>> ans = new ArrayList<>();
    for (int i = start; i < s.length(); i++) {
        if (dp[start][i]) {      // 看s[start...i]是否回文
            String left = s.substring(start, i + 1);
            for (List<String> l : partitionHelper(s, i + 1, dp)) {
                l.add(0, left);
                ans.add(l);
            }
        }
    }
    return ans;
}

解法3：回溯算法

private List<List<String>> ans = new ArrayList<>();
public List<List<String>> partition(String s) {
    int n = s.length();
    // 长度和起始位置确定是否为回文（动态规划）
    boolean[][] dp = new boolean[n][n];
    for (int len = 1; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            dp[i][i + len - 1] = s.charAt(i) == s.charAt(i + len - 1) && (len < 3 || dp[i + 1][i + len - 2]);
        }
    }

    partitionHelper(s, 0, dp, new ArrayList<>());
    return ans;
}

private void partitionHelper(String s, int start, boolean[][] dp, List<String> temp) {
    if (start == s.length()) {
        ans.add(new ArrayList<>(temp));
    }

    for (int i = start; i < s.length(); i++) {
        if (dp[start][i]) {
            String left = s.substring(start, i + 1);
            temp.add(left);
            partitionHelper(s, i + 1, dp, temp);
            temp.remove(temp.size() - 1);  // 撤销选择
        }

    }
}

9.分割回文串ii（132-难）

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回符合要求的最少分割次数。

示例：

输入: "aab"
输出: 1
解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

思路分析：本题涉及最少分割次数，显然是一个动态规划问题。确定回文串参考8的动态规划解法。分析如下：

• dp[i]：以下标i作为结尾的最少的分割次数；
• 确定递推关系：不失一般性，我们考虑j (j < i)字符（分割点）的分割方案。确定动态规划的状态转移方程：
  • 假设[0, i]已经是回文了，则dp[i] = 0。
  • 否则需要考虑j位置，判断[j + 1, i]是否为回文子串，如果是，那么以i作为结尾的最少分割次数为dp[i] = min(dp[i], dp[j] + 1)；

那么待解决的问题就是如何判断[j + 1, i]是回文子串，若字符串长度较大，那么双指针时间复杂度过高（与647不同）

这里可以使用动态规划求回文子串。子串[j, i]是回文子串必须同时满足下面两个条件：

• [j + 1, i - 1] 是回文子串或j -i <= 1；
• s.charAt(i) == s.charAt(j)，当长度小于等于2只需满足此项。

从根据依赖关系从左下角至右上角依次填表，确定子串是否回文。

代码实现：

public int minCut(String s) {
    int n = s.length();
    boolean[][] isPalindrome = new boolean[n][n];
    for (int i = n - 1; i >= 0; --i) {
        for (int j = i; j < n; ++j) {
            if (s.charAt(i) == s.charAt(j) && (j - i <= 1 || isPalindrome[i + 1][j - 1])) {
                isPalindrome[i][j] = true;
            }
        }
    }
    // 初始化dp数组
    int[] dp = new int[n];
    for (int i = 0; i < n; ++i) dp[i] = i;

    for (int i = 1; i < n; ++i) {
        if (isPalindrome[0][i]) {
            dp[i] = 0;
            continue;
        }
        for (int j = 0; j < i; ++j) {
            if (isPalindrome[j + 1][i]) {
                dp[i] = Math.min(dp[i], dp[j] + 1);
            }
        }
    }
    return dp[n - 1];
}