c++设计,给定一个字符串 s,你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。 示例 1: 输入:s = "aacecaaa" 输出:"aaacecaaa" 示例 2: 输入:s = "abcd" 输出:"dcbabcd"
时间: 2023-07-19 13:51:26 浏览: 64
这是一个经典的字符串问题,可以通过 Manacher 算法来解决,时间复杂度为 O(n)。
具体思路如下:
1. 将原字符串翻转得到反转字符串
2. 将原字符串和反转字符串拼接起来,并且在它们中间插入一个特殊字符,比如 #,得到新的字符串 t
3. 对新字符串 t 进行 Manacher 算法,得到每个字符为中心的最长回文半径数组 p
4. 找到最长回文半径 p[len-1],它表示 t 中以最后一个字符为中心的最长回文半径
5. 截取反转字符串的前缀 len - p[len-1],并将其拼接到原字符串的前面,得到最短回文串
代码实现如下:
相关问题
给定一个字符串 s,你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。 示例 1: 输入:s = "aacecaaa" 输出:"aaacecaaa" 示例 2: 输入:s = "abcd" 输出:"dcbabcd",输出设计代码
以下是 C++ 代码实现:
```cpp
class Solution {
public:
string shortestPalindrome(string s) {
int n = s.length();
string r = s;
reverse(r.begin(), r.end()); // 反转字符串
string t = s + "#" + r + "#"; // 插入特殊字符
int m = t.length();
vector<int> p(m);
int center = 0, right = 0;
for (int i = 1; i < m - 1; i++) {
int j = 2 * center - i;
if (right > i) {
p[i] = min(right - i, p[j]);
}
while (t[i + p[i] + 1] == t[i - p[i] - 1]) {
p[i]++;
}
if (i + p[i] > right) {
center = i;
right = i + p[i];
}
}
int len = p[m - 2];
return r.substr(0, n - len) + s;
}
};
```
算法的详细解释可以参考我写的博客文章:[LeetCode 214. Shortest Palindrome](https://www.cnblogs.com/grandyang/p/4523624.html)。
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。给出c++代码
以下是给定字符串 s,找出其中不含有重复字符的最长子串的长度的 C++ 代码示例:
```cpp
#include <iostream>
#include <unordered_set>
int lengthOfLongestSubstring(std::string s) {
int n = s.length();
int maxLength = 0;
int left = 0, right = 0;
std::unordered_set<char> charSet;
while (right < n) {
if (charSet.find(s[right]) == charSet.end()) {
charSet.insert(s[right]);
maxLength = std::max(maxLength, right - left + 1);
right++;
} else {
charSet.erase(s[left]);
left++;
}
}
return maxLength;
}
int main() {
std::string s = "abcabcbb";
int length = lengthOfLongestSubstring(s);
std::cout << "Length of longest substring without repeating characters: " << length << std::endl;
return 0;
}
```
该代码使用滑动窗口的思想,在遍历字符串时维护一个窗口,窗口内的字符不重复。通过两个指针 `left` 和 `right` 来表示窗口的左边界和右边界。使用 `unordered_set` 来存储窗口内的字符,以便进行查找和删除操作。
逐个字符遍历字符串,如果当前字符在窗口中不存在,则将该字符加入窗口,并更新最大长度。如果当前字符已经存在于窗口中,则将窗口左边界向右移动一位,并删除左边界对应的字符,直到当前字符不再重复为止。
最终,返回的 `maxLength` 即为最长不含重复字符的子串的长度。
在示例中,字符串 "abcabcbb" 的最长不含重复字符的子串是 "abc",因此输出结果为 3。