最小的子串需要被删除才能使给定的字符串成为回文-C++-PHP中文网

最小的子串需要被删除才能使给定的字符串成为回文

PHPz

发布： 2023-08-30 17:49:03

转载

1378人浏览过

最小的子串需要被删除才能使给定的字符串成为回文

回文是一种正向和反向读取都相同的字符序列。在计算机科学和编程中，回文是字符串操作问题中常见的主题。在本文中，我们将探讨如何找到必须从给定字符串中删除的最小大小的子串，使其成为回文。我们将提供一个结构良好的C++解决方案，并包含一个示例来说明测试用例。

问题陈述

给定长度为'n'的字符串's'，我们需要找到应该删除的子字符串的最小大小，以使剩下的字符串成为回文。

算法

创建一个名为isPalindrome的函数，它以字符串's'作为参数，并在其为回文时返回true，否则返回false。
创建一个名为minSizeSubstringToRemove的函数，它以字符串's'作为参数。
将变量'minSize'初始化为字符串的长度。
使用循环迭代字符串，从0到'n'递增一个索引'i'。
在每次迭代中，执行以下步骤 −

从字符串的开头到索引'i'创建两个子字符串，另一个从索引'i'到字符串的末尾。
检查其中任意一个子字符串是否为回文。
如果任一子字符串是回文，将'minSize'更新为非回文子字符串的长度和'minSize'之间的最小值。

将'minSize'作为结果返回。

示例

#include <iostream>
#include <string>
#include <algorithm>

// Function to check if a string is a palindrome
bool isPalindrome(const std::string &s) {
   int left = 0;
   int right = s.length() - 1;
   
   while (left < right) {
      if (s[left] != s[right]) {
         return false;
      }
      ++left;
      --right;
   }
   
   return true;
}

// Function to find the minimum size substring to be removed
int minSizeSubstringToRemove(std::string s) {
   int n = s.length();
   int minSize = n;
   
   for (int i = 0; i <= n; ++i) {
      std::string leftSubstring = s.substr(0, i);
      std::string rightSubstring = s.substr(i, n - i);
   
      if (isPalindrome(leftSubstring)) {
         minSize = std::min(minSize, static_cast<int>(rightSubstring.length()));
      }
      if (isPalindrome(rightSubstring)) {
         minSize = std::min(minSize, static_cast<int>(leftSubstring.length()));
      }
   }
   
   return minSize;
}

int main() {
   std::string s = "abccbaab";
   int result = minSizeSubstringToRemove(s);
   std::cout << "Minimum size substring to be removed: " << result << std::endl;
   
   return 0;
}

登录后复制

输出

Minimum size substring to be removed: 2

登录后复制

测试用例示例

考虑以下字符串："abccbaab"。可能的子字符串及其对应的回文状态如下：

左子字符串 = ""，右子字符串 = "abccbaab"，回文 = false

Kimi智能助手
超强AI写作助手，一键总结20w字长文，支持批量文档上传，多端同步内容不怕丢失。论文综述、文档速读、脚本小说创作，统统交给Kimi！实时联网搜索，给你最智能清晰的解答。

1671

查看详情
左子串 = "a"，右子串 = "bccbaab"，回文 = false
左子串 = "ab"，右子串 = "ccbaab"，回文 = false
左子串 = "abc"，右子串 = "cbaab"，回文 = false
左子串 = "abcc"，右子串 = "baab"，回文 = false
左子串 = "abccb"，右子串 = "aab"，回文 = true（左子串）
左子字符串 = "abccba"，右子字符串 = "ab"，回文 = true（左子字符串）
左子字符串 = "abccbaa"，右子字符串 = "b"，回文 = false
左子串 = "abccbaab"，右子串 = ""，回文 = false