多组数据,每组数据给你一个字符串,你可以删除任意次,每次删除一个长度大于等于 2 的回文串,问能否删空整个字符串。c++代码
时间: 2024-10-05 19:03:50 浏览: 64
在 C++ 中,处理这种问题通常会涉及到动态规划或者使用栈来辅助判断。下面是一个简单的思路,我们可以遍历每个字符串,对于每个位置 i,检查从 i 到结尾的子串是否为回文,如果是,则尝试删除它。如果所有子串都可以通过删除回文串变为空,那么原字符串就可以变成空。
这是一个基础的算法描述,具体的 C++ 代码如下:
```cpp
#include <iostream>
#include <string>
bool isPalindrome(const std::string &s) {
int start = 0, end = s.size() - 1;
while (start < end) {
if (s[start] != s[end]) return false;
start++;
end--;
}
return true;
}
bool canEmptyString(const std::vector<std::string> &strings) {
for (const auto &str : strings) {
if (!isPalindrome(str)) continue; // 如果不是回文直接跳过
bool canDelete = true;
for (int i = 1; i < str.size(); i++) { // 遍历寻找最长回文串
if (isPalindrome(str.substr(i))) { // 如果找到,尝试删除
str.erase(i, str.size() - i); // 删除回文部分
canDelete &= canEmptyString(strings); // 递归检查剩余部分
if (canDelete) break; // 只需删除一次就足够
}
}
if (!canDelete) return false; // 无法删除回文导致无法变为空字符串
}
return true;
}
int main() {
std::vector<std::string> inputStrings = {"aba", "abc"};
if (canEmptyString(inputStrings)) {
std::cout << "可以删除回文串将所有字符串变为空。\n";
} else {
std::cout << "无法删除回文串将所有字符串变为空。\n";
}
return 0;
}
```
阅读全文