算法 - 回文相关

快来打我* 2022-11-12 13:54 110阅读 0赞

### 文章目录 ###

*  1.判断是否回文
 *  2.最长回文子串
 *  3.分割回文串
 *  4.最短回文串
 *  Manacher 算法 O（n）
 *  KMP算法

# 1.判断是否回文 #

双指针做法的时间复杂度是 O(N)，优化的解法是，先采用动态规划，把回文子串的结果记录在一个表格里。

/** * * @param charArray * @param left 子串的左边界，可以取到 * @param right 子串的右边界，可以取到 * @return */
        private boolean checkPalindrome(char[] charArray, int left, int right) { 
            while (left < right) { 
                if (charArray[left] != charArray[right]) { 
                    return false;
                }
                left++;
                right--;
            }
            return true;
        }

其次就是有关链表的回文分析，判断单链表是否是一个回文串。  
解法1就是将链表中的数据移到数组中进行判断。略。空间O（n）。  
解法2使用递归反向迭代节点，同时使用递归函数外的变量向前迭代，就可以判断链表是否为回文。空间复杂度仍然是O（n），因为使用了堆栈的空间。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70]  
图片来自leetcode

private ListNode frontPointer;
    
        private boolean recursivelyCheck(ListNode currentNode) { 
            if (currentNode != null) { 
                if (!recursivelyCheck(currentNode.next)) { 
                    return false;
                }
                if (currentNode.val != frontPointer.val) { 
                    return false;
                }
                frontPointer = frontPointer.next;
            }
            return true;
        }
    
        public boolean isPalindrome(ListNode head) { 
            frontPointer = head;
            return recursivelyCheck(head);
        }

[leetcode链接][leetcode]  
解法3：便是链表里十分常见的快慢指针。  
思路很简单，使用快慢指针获取到后半段链表，将后半段链表进行反转，再与前半段进行比较。

public boolean isPalindrome(ListNode head) { 
            if (head == null) { 
                return true;
            }
    
            // 找到前半部分链表的尾节点并反转后半部分链表
            ListNode firstHalfEnd = endOfFirstHalf(head);
            ListNode secondHalfStart = reverseList(firstHalfEnd.next);
    
            // 判断是否回文
            ListNode p1 = head;
            ListNode p2 = secondHalfStart;
            boolean result = true;
            while (result && p2 != null) { 
                if (p1.val != p2.val) { 
                    result = false;
                }
                p1 = p1.next;
                p2 = p2.next;
            }        
    
            // 还原链表并返回结果
            firstHalfEnd.next = reverseList(secondHalfStart);
            return result;
        }
    
        private ListNode reverseList(ListNode head) { 
            ListNode prev = null;
            ListNode curr = head;
            while (curr != null) { 
                ListNode nextTemp = curr.next;
                curr.next = prev;
                prev = curr;
                curr = nextTemp;
            }
            return prev;
        }
    
        private ListNode endOfFirstHalf(ListNode head) { 
            ListNode fast = head;
            ListNode slow = head;
            while (fast.next != null && fast.next.next != null) { 
                fast = fast.next.next;
                slow = slow.next;
            }
            return slow;
        }

# 2.最长回文子串 #

[leetcde链接][leetcde]  
最长回文子串最经典的解法就是动态规划，这也是动态规划学习中的一道经典例题。  
使用动态规划的关键是需要分析出该方法的动态转移方程，结合题意。我们可以很清楚的分析出，如果子串长度大于3，那么该子串的其去头尾后仍然是一个回文串，依次递归下去，最终问题仍然回到了子串长度为1与2的情况。  
那么我们的动态方程就可以写出来了：

f（i,j） = 
    {
     ture , i-j=0
     c(i)==c(j),j-i =1
     c(i)==c(j)&&f(i+1,j-1) ,j-i >1
    }

通过以上分析，我们知道我们依赖于 子串长度为1与2的情况，故我们使用l当作外围函数，逐次获取子串长度慢慢变大的情况，且通过dp【i】【j】记录i-j 是否为子串。

public String longestPalindrome(String s) { 
            int n = s.length();
            boolean[][] dp = new boolean[n][n];
            String ans = "";
            // l 代表迭代子串长度
            for (int l = 0; l < n; ++l) { 
                for (int i = 0; i + l < n; ++i) { 
                // 获取j的索引位置 j==i+l 长度
                    int j = i + l;
                    if (l == 0) { 
                        dp[i][j] = true;
                    } else if (l == 1) { 
                        dp[i][j] = (s.charAt(i) == s.charAt(j));
                    } else { 
                        dp[i][j] = (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]);
                    }
                    if (dp[i][j] && l + 1 > ans.length()) { 
                        ans = s.substring(i, i + l + 1);
                    }
                }
            }
            return ans;
        }

番外话，贴一个lc上weiwei大佬的动态规划总结图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70 1]  
还有一种解法就是中心扩散方法，遍历每一个索引，以这个索引为中心，利用“回文串”中心对称的特点，往两边扩散，看最多能扩散多远。  
只是需要注意的是回文串在长度为奇数和偶数的时候，“回文中心”的形式是不一样的。

public String longestPalindrome(String s) { 
            int len = s.length();
            if (len < 2) { 
                return s;
            }
            int maxLen = 1;
            String res = s.substring(0, 1);
            // 中心位置枚举到 len - 2 即可
            for (int i = 0; i < len - 1; i++) { 
                String oddStr = centerSpread(s, i, i);
                String evenStr = centerSpread(s, i, i + 1);
                String maxLenStr = oddStr.length() > evenStr.length() ? oddStr : evenStr;
                if (maxLenStr.length() > maxLen) { 
                    maxLen = maxLenStr.length();
                    res = maxLenStr;
                }
            }
            return res;
        }
    
        private String centerSpread(String s, int left, int right) { 
            // left = right 的时候，此时回文中心是一个字符，回文串的长度是奇数
            // right = left + 1 的时候，此时回文中心是一个空隙，回文串的长度是偶数
            int len = s.length();
            int i = left;
            int j = right;
            while (i >= 0 && j < len) { 
                if (s.charAt(i) == s.charAt(j)) { 
                    i--;
                    j++;
                } else { 
                    break;
                }
            }
            // 这里要小心，跳出 while 循环时，恰好满足 s.charAt(i) != s.charAt(j)，因此不能取 i，不能取 j
            return s.substring(i + 1, j);
        }

# 3.分割回文串 #

[leetcode weiwei][]

> 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。  
> 输入：s = “aab”  
> 输出：\[\[“a”,“a”,“b”\],\[“aa”,“b”\]\]

这一道题从乍一看其实就是一道回溯的算法，但是在优化上，结合回文串的判断可以进行预处理的优化。  
总的结合就是 dp加回溯。

public List<List<String>> partition(String s) { 
            int len = s.length();
            List<List<String>> res = new ArrayList<>();
            if (len == 0) { 
                return res;
            }
    
            // Stack 这个类 Java 的文档里推荐写成 Deque<Integer> stack = new ArrayDeque<Integer>();
            // 注意：只使用 stack 相关的接口
            Deque<String> stack = new ArrayDeque<>();
            char[] charArray = s.toCharArray();
            dfs(charArray, 0, len, stack, res);
            return res;
        }
    
        /** * @param charArray * @param index 起始字符的索引 * @param len 字符串 s 的长度，可以设置为全局变量 * @param path 记录从根结点到叶子结点的路径 * @param res 记录所有的结果 */
        private void dfs(char[] charArray, int index, int len, Deque<String> path, List<List<String>> res) { 
            if (index == len) { 
                res.add(new ArrayList<>(path));
                return;
            }
    
            for (int i = index; i < len; i++) { 
                // 因为截取字符串是消耗性能的，因此，采用传子串下标的方式判断一个子串是否是回文子串
                if (!checkPalindrome(charArray, index, i)) { 
                    continue;
                }
                path.addLast(new String(charArray, index, i + 1 - index));
                dfs(charArray, i + 1, len, path, res);
                path.removeLast();
            }
        }
    
        /** * 这一步的时间复杂度是 O(N)，优化的解法是，先采用动态规划，把回文子串的结果记录在一个表格里 * * @param charArray * @param left 子串的左边界，可以取到 * @param right 子串的右边界，可以取到 * @return */
        private boolean checkPalindrome(char[] charArray, int left, int right) { 
            while (left < right) { 
                if (charArray[left] != charArray[right]) { 
                    return false;
                }
                left++;
                right--;
            }
            return true;
        }

优化后的预处理代码如下：

public List<List<String>> partition(String s) { 
            int len = s.length();
            List<List<String>> res = new ArrayList<>();
            if (len == 0) { 
                return res;
            }
    
            char[] charArray = s.toCharArray();
            // 预处理
            // 状态：dp[i][j] 表示 s[i][j] 是否是回文
            boolean[][] dp = new boolean[len][len];
            // 状态转移方程：在 s[i] == s[j] 的时候，dp[i][j] 参考 dp[i + 1][j - 1]
            for (int right = 0; right < len; right++) { 
                // 注意：left <= right 取等号表示 1 个字符的时候也需要判断
                for (int left = 0; left <= right; left++) { 
                    if (charArray[left] == charArray[right] && (right - left <= 2 || dp[left + 1][right - 1])) { 
                        dp[left][right] = true;
                    }
                }
            }
    
            Deque<String> stack = new ArrayDeque<>();
            dfs(s, 0, len, dp, stack, res);
            return res;
        }
    
        private void dfs(String s, int index, int len, boolean[][] dp, Deque<String> path, List<List<String>> res) { 
            if (index == len) { 
                res.add(new ArrayList<>(path));
                return;
            }
    
            for (int i = index; i < len; i++) { 
                if (dp[index][i]) { 
                    path.addLast(s.substring(index, i + 1));
                    dfs(s, i + 1, len, dp, path, res);
                    path.removeLast();
                }
            }
        }

--------------------

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

两次dp，第一次dp预处理s字符床，第二次dp，f\[i\] 代表分割\[0…i\]的最小次数。

class Solution { 
        public int minCut(String s) { 
            int n = s.length();
            char[] cs = s.toCharArray();
    
            // 预处理出 st，st[i][j] 表示区间 [i,j] 是否为回文串
            boolean[][] st = new boolean[n][n]; 
            for (int j = 0; j < n; j++) { 
                for (int i = j; i >= 0; i--) { 
                    // 当 [i, j] 只有一个字符时，必然是回文串
                    if (i == j) { 
                        st[i][j] = true;
                    } else { 
                        // 当 [i, j] 长度为 2 时，满足 cs[i] == cs[j] 即回文串
                        if (j - i + 1 == 2) { 
                            st[i][j] = cs[i] == cs[j];
    
                        // 当 [i, j] 长度大于 2 时，满足 (cs[i] == cs[j] && f[i + 1][j - 1]) 即回文串
                        } else { 
                            st[i][j] = cs[i] == cs[j] && st[i + 1][j - 1];
                        }
                    }
                }
            }
    
            // f(i) 代表考虑下标为 i 的字符为结尾的最小分割次数
            int[] f = new int[n]; 
            for (int j = 1; j < n; j++) { 
    
                // 如果 [0,j] 这一段直接构成回文，则无须分割
                if (st[0][j]) {  
                    f[j] = 0;
    
                // 如果无法直接构成回文
                // 那么对于第 j 个字符，有使用分割次数，或者不使用分割次数两种选择
                } else {  
                    // 下边两种决策也能够合到一个循环当中去做，但是需要先将 f[i] 预设为一个足够大的数，因此干脆拆开来做
    
                    // 独立使用一次分割次数
                    f[j] = f[j - 1] + 1;
    
                    // 第 j 个字符本身不独立使用分割次数
                    // 代表要与前面的某个位置 i 形成区间 [i,j]，使得 [i, j] 形成回文，[i, j] 整体消耗一次分割次数
                    for (int i = 1; i < j; i++) { 
                        if (st[i][j]) { 
                            f[j] = Math.min(f[j], f[i - 1] + 1);
                        }
                    }
                }
            }
            return f[n - 1];
        }
    }

# 4.最短回文串 #

[leetcode][leetcode 1]

> 给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。

此题分析思路不出错，根本问题为找到s的最长回文前缀。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70 2]  
最后返回 s+prefix即可。  
但如何找出最长前缀是个问题。这里取lc提供的lc字符串哈希方法做介绍：  
在该方法中，我们将字符串看成一个 base 进制的数，它对应的十进制值就是哈希值。显然，两个字符串的哈希值相等，当且仅当这两个字符串本身相同。然而如果字符串本身很长，其对应的十进制值在大多数语言中无法使用内置的整数类型进行存储。因此，我们会将十进制值对一个大质数 mod 进行取模。

代码如下：

class Solution { 
        public String shortestPalindrome(String s) { 
            int n = s.length();
            int base = 131, mod = 1000000007;
            int left = 0, right = 0, mul = 1;
            int best = -1;
            for (int i = 0; i < n; ++i) { 
                left = (int) (((long) left * base + s.charAt(i)) % mod);
                right = (int) ((right + (long) mul * s.charAt(i)) % mod);
                if (left == right) { 
                    best = i;
                }
                mul = (int) ((long) mul * base % mod);
            }
            String add = (best == n - 1 ? "" : s.substring(best + 1));
            StringBuffer ans = new StringBuffer(add).reverse();
            ans.append(s);
            return ans.toString();
        }
    }

还有一个思路kmp算法解决如下：

class Solution { 
        public String shortestPalindrome(String s) { 
            int n = s.length();
            int[] fail = new int[n];
            Arrays.fill(fail, -1);
            for (int i = 1; i < n; ++i) { 
                int j = fail[i - 1];
                while (j != -1 && s.charAt(j + 1) != s.charAt(i)) { 
                    j = fail[j];
                }
                if (s.charAt(j + 1) == s.charAt(i)) { 
                    fail[i] = j + 1;
                }
            }
            int best = -1;
            for (int i = n - 1; i >= 0; --i) { 
                while (best != -1 && s.charAt(best + 1) != s.charAt(i)) { 
                    best = fail[best];
                }
                if (s.charAt(best + 1) == s.charAt(i)) { 
                    ++best;
                }
            }
            String add = (best == n - 1 ? "" : s.substring(best + 1));
            StringBuffer ans = new StringBuffer(add).reverse();
            ans.append(s);
            return ans.toString();
        }
    }

# Manacher 算法 O（n） #

[Manacher 算法][leetcde]

为了表述方便，我们定义一个新概念臂长，表示中心扩展算法向外扩展的长度。如果一个位置的最大回文字符串长度为 2 \* length + 1 ，其臂长为 length。

下面的讨论只涉及长度为奇数的回文字符串。长度为偶数的回文字符串我们将会在最后与长度为奇数的情况统一起来。

**思路与算法**

在中心扩展算法的过程中，我们能够得出每个位置的臂长。那么当我们要得出以下一个位置 i 的臂长时，能不能利用之前得到的信息呢？

答案是肯定的。具体来说，如果位置 j 的臂长为 length，并且有 j + length > i，如下图所示

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70 3]  
当在位置 i 开始进行中心拓展时，我们可以先找到 i 关于 j 的对称点 2 \* j - i。那么如果点 2 \* j - i 的臂长等于 n，我们就可以知道，点 i 的臂长至少为 min(j + length - i, n)。那么我们就可以直接跳过 i 到 i + min(j + length - i, n) 这部分，从 i + min(j + length - i, n) + 1 开始拓展。

我们只需要在中心扩展法的过程中记录右臂在最右边的回文字符串，将其中心作为 j，在计算过程中就能最大限度地避免重复计算。

那么现在还有一个问题：如何处理长度为偶数的回文字符串呢？

我们可以通过一个特别的操作将奇偶数的情况统一起来：我们向字符串的头尾以及每两个字符中间添加一个特殊字符 \#，比如字符串 aaba 处理后会变成 \#a\#a\#b\#a\#。那么原先长度为偶数的回文字符串 aa 会变成长度为奇数的回文字符串 \#a\#a\#，而长度为奇数的回文字符串 aba 会变成长度仍然为奇数的回文字符串 \#a\#b\#a\#，我们就不需要再考虑长度为偶数的回文字符串了。

注意这里的特殊字符不需要是没有出现过的字母，我们可以使用任何一个字符来作为这个特殊字符。这是因为，当我们只考虑长度为奇数的回文字符串时，每次我们比较的两个字符奇偶性一定是相同的，所以原来字符串中的字符不会与插入的特殊字符互相比较，不会因此产生问题。

public String longestPalindrome(String s) { 
            int start = 0, end = -1;
            StringBuffer t = new StringBuffer("#");
            for (int i = 0; i < s.length(); ++i) { 
                t.append(s.charAt(i));
                t.append('#');
            }
            t.append('#');
            s = t.toString();
    
            List<Integer> arm_len = new ArrayList<Integer>();
            int right = -1, j = -1;
            for (int i = 0; i < s.length(); ++i) { 
                int cur_arm_len;
                if (right >= i) { 
                    int i_sym = j * 2 - i;
                    int min_arm_len = Math.min(arm_len.get(i_sym), right - i);
                    cur_arm_len = expand(s, i - min_arm_len, i + min_arm_len);
                } else { 
                    cur_arm_len = expand(s, i, i);
                }
                arm_len.add(cur_arm_len);
                if (i + cur_arm_len > right) { 
                    j = i;
                    right = i + cur_arm_len;
                }
                if (cur_arm_len * 2 + 1 > end - start) { 
                    start = i - cur_arm_len;
                    end = i + cur_arm_len;
                }
            }
    
            StringBuffer ans = new StringBuffer();
            for (int i = start; i <= end; ++i) { 
                if (s.charAt(i) != '#') { 
                    ans.append(s.charAt(i));
                }
            }
            return ans.toString();
        }
    
        public int expand(String s, int left, int right) { 
            while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) { 
                --left;
                ++right;
            }
            return (right - left - 2) / 2;
        }
    }

# KMP算法 #

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70]: /images/20221022/0511ab4b126541dfa116f98de30fd67d.png
[leetcode]: https://leetcode-cn.com/problems/palindrome-linked-list/solution/hui-wen-lian-biao-by-leetcode-solution/
[leetcde]: https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70 1]: /images/20221022/8fce87f64aa947b0a786c00ba974db4b.png
[leetcode weiwei]: https://leetcode-cn.com/problems/palindrome-partitioning/solution/hui-su-you-hua-jia-liao-dong-tai-gui-hua-by-liweiw/249294/
[leetcode 1]: https://leetcode-cn.com/problems/shortest-palindrome/solution/zui-duan-hui-wen-chuan-by-leetcode-solution/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70 2]: /images/20221022/74a52654b3124bd6a2fce32b906502e3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70 3]: /images/20221022/211693cd24ae4ad2bb700e3906440ff7.png