最短回文串

难度:

标签:

题目描述

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

示例 1：

输入：s = "aacecaaa"
输出："aaacecaaa"

示例 2：

输入：s = "abcd"
输出："dcbabcd"

提示：

0 <= s.length <= 5 * 10⁴
s 仅由小写英文字母组成

代码结果

运行时间: 41 ms, 内存: 16.2 MB

// 思路：
// 1. 使用相同的思路，将s反转并构建最长回文前缀，
//    但使用Java Stream处理字符串操作
 
import java.util.stream.IntStream;
import java.util.stream.Collectors;
 
public class SolutionStream {
    public String shortestPalindrome(String s) {
        int n = s.length();
        String reverse_s = new StringBuilder(s).reverse().toString();
        String combined = s + "#" + reverse_s;
        int[] prefix = new int[combined.length()];
 
        IntStream.range(1, combined.length()).forEach(i -> {
            int j = prefix[i - 1];
            while (j > 0 && combined.charAt(i) != combined.charAt(j)) {
                j = prefix[j - 1];
            }
            if (combined.charAt(i) == combined.charAt(j)) {
                j++;
            }
            prefix[i] = j;
        });
 
        return IntStream.range(0, n - prefix[combined.length() - 1])
                        .mapToObj(reverse_s::charAt)
                        .map(String::valueOf)
                        .collect(Collectors.joining()) + s;
    }
}

解释

方法:

这个题解采用了二分查找的思路。首先将原字符串 s 翻转得到 s1。如果 s 本身就是回文串，直接返回 s。否则，通过二分查找的方式，在 s1 中查找 s 的前缀，找到最长的能够形成回文串的前缀。查找过程中，使用双指针 a 和 b 分别指向查找范围的起始和结束位置，每次取中点 c，判断 s1 中是否存在 s[:c] 子串。如果存在，则判断 s1[j+c:j+m] 与 s[c:m] 是否相等（其中 j 为 s[:c] 在 s1 中的起始位置，m 为 s[:c] 的中点），如果相等则找到了最长的回文前缀，返回 s1[:j] + s。如果不相等，则将查找范围缩小到 [c, b]。如果 s[:c] 在 s1 中不存在，则将查找范围缩小到 [a, c-1]。最后，如果没有找到任何回文前缀，则返回 s1[:-1] + s。

时间复杂度:

O(n log n)

空间复杂度:

O(n)

代码细节讲解

🦆

为什么要将原字符串翻转得到 s1 来进行处理？这样做的目的是什么？

▷

将原字符串 s 翻转得到 s1 主要是为了方便查找和确认 s 的前缀是否能与 s1 的后缀匹配，从而构成回文。回文的特性是前后对称，所以通过比较原字符串的前缀与翻转字符串的后缀（实际上在翻转字符串中的位置相当于前缀），可以有效地判定最长的回文前缀。这种方法简化了判断过程，避免了复杂的回文判断操作，提高了效率。

🦆

在二分查找中，你是如何确定查找区间 [a, b] 的初始值及其调整逻辑的？

▷

查找区间 [a, b] 的初始值是基于最坏情况的考虑，即寻找直到中点的前缀以检查其中可能的最长回文前缀。初始值设置为从 1 到 n//2 主要是因为回文前缀的长度至少为 1 且最长不会超过字符串长度的一半。查找区间的调整逻辑是基于二分查找的原理，每次根据中点 c 的判断结果来缩小查找范围，如果 s[:c] 在 s1 中位置不合法或不存在，说明当前 c 作为回文前缀的可能性较小，因此调整查找范围到 [a, c-1]。

🦆

当 s1.find(s[:c]) 返回 -1 时，为什么选择将查找范围调整到 [a, c-1] 而不是其他区间？

▷

当 s1.find(s[:c]) 返回 -1 时，这意味着 s[:c] 这个前缀在 s1 中没有找到匹配的子串，即 s1 中不存在以该前缀结束的子串。因此，任何长于 c 的前缀也不可能在 s1 中找到匹配的子串。所以，为了找到可能存在的最长回文前缀，我们需要缩短前缀长度，即将查找范围调整到 [a, c-1]，继续在更短的前缀中寻找匹配。

🦆

算法中提到，如果 s1[j+c:j+m] 与 s[c:m] 相等，则找到了最长的回文前缀。这里的判断逻辑是怎样的？能否详细解释一下这部分的比较机制？

▷

在这部分的逻辑中，s1[j+c:j+m] 与 s[c:m] 的比较是为了确认在找到 s[:c] 在 s1 中的匹配后，这个匹配是否能扩展到更长的回文。具体来说，j 是 s[:c] 在 s1 中的起始位置，c 是当前考虑的前缀长度，m 是 s1 中匹配的结束位置的中点。这个比较确认从 j+c 到 j+m 的子串是否与 s 从 c 到 m 的子串相等，如果相等，说明 s 的起始部分到 m 可以和 s1 的相应部分形成回文，因此这部分 s 加上 s1 的前 j 个字符（即 s1 中与 s 前缀相匹配的部分之前的字符）构成了所求的最短回文串。

相关问题

最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成

找出字符串中第一个匹配项的下标

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

示例 1：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

提示：

1 <= haystack.length, needle.length <= 10⁴
haystack 和 needle 仅由小写英文字符组成

回文对

给定一个由唯一字符串构成的 0 索引 数组 words 。

回文对 是一对整数 (i, j) ，满足以下条件：

0 <= i, j < words.length，
i != j ，并且
words[i] + words[j]（两个字符串的连接）是一个回文串。

返回一个数组，它包含 words 中所有满足 回文对 条件的字符串。

你必须设计一个时间复杂度为 O(sum of words[i].length) 的算法。

示例 1：

输入：words = ["abcd","dcba","lls","s","sssll"]
输出：[[0,1],[1,0],[3,2],[2,4]] 
解释：可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]

示例 2：

输入：words = ["bat","tab","cat"]
输出：[[0,1],[1,0]] 
解释：可拼接成的回文串为 ["battab","tabbat"]

示例 3：

输入：words = ["a",""]
输出：[[0,1],[1,0]]

提示：

1 <= words.length <= 5000
0 <= words[i].length <= 300
words[i] 由小写英文字母组成

打家劫舍 II 数组中的第K个最大元素