移除最小长度子串以使给定字符串成为回文

回文是指正读和反读都一样的字符序列。在计算机科学和编程中，回文是字符串操作问题的常见主题。在本文中，我们将探讨查找必须从给定字符串中移除的最小长度子串以使其成为回文的问题。我们将包含一个示例来说明测试用例。

问题陈述

给定一个长度为'n'的字符串's'，我们需要找到应移除的子串的最小长度，以使剩余的字符串成为回文。

算法

  • 创建一个名为isPalindrome的函数，该函数接受字符串's'作为参数，如果它是回文则返回true，否则返回false。

  • 创建一个名为minSizeSubstringToRemove的函数，该函数接受字符串's'作为参数。

  • 将变量'minSize'初始化为字符串的长度。

  • 使用循环遍历字符串，将索引'i'从0递增到'n'。

  • 在每次迭代中，执行以下步骤：

    • 创建两个子串：一个是从字符串的开头到索引'i'，另一个是从索引'i'到字符串的结尾。

    • 检查任一子串是否为回文。

    • 如果任一子串是回文，则将'minSize'更新为'minSize'和非回文子串长度之间的最小值。

  • 返回'minSize'作为结果。

示例

以下是此算法在各种编程语言中的实现：

C C++ Java Python
Open Compiler
#include <stdio.h>
#include <string.h>

// Function to check if a string is a palindrome
int isPalindrome(const char *s, int left, int right) {
   while (left < right) {
      if (s[left] != s[right]) {
         return 0;
      }
      ++left;
      --right;
   }
   return 1;
}

// Function to find the minimum size substring to be removed
int minSizeSubstringToRemove(const char *s) {
   int n = strlen(s);
   int minSize = n;

   for (int i = 0; i <= n; ++i) {
      // Splitting the string into left and right substrings
      char leftSubstring[100];
      strncpy(leftSubstring, s, i);
      leftSubstring[i] = '\0';

      char rightSubstring[100];
      strncpy(rightSubstring, s + i, n - i);
      rightSubstring[n - i] = '\0';

      if (isPalindrome(leftSubstring, 0, i - 1)) {
         minSize = (n - i) < minSize ? (n - i) : minSize;
      }
      if (isPalindrome(rightSubstring, 0, n - i - 1)) {
         minSize = i < minSize ? i : minSize;
      }
   }
   return minSize;
}
int main() {
   char s[] = "abccbaab";
   int result = minSizeSubstringToRemove(s);
   printf("Minimum size substring to be removed: %d\n", result);

   return 0;
}

输出

Minimum size substring to be removed: 2
Open Compiler
#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
Open Compiler
public class Main {
   // Function to check if a string is a palindrome
   private static boolean isPalindrome(String s, int left, int right) {
      while (left < right) {
         if (s.charAt(left) != s.charAt(right)) {
            return false;
         }
         left++;
         right--;
      }
      return true;
   }

   // Function to find the minimum size substring to be removed
   private static int minSizeSubstringToRemove(String s) {
      int n = s.length();
      int minSize = n;

      for (int i = 0; i <= n; i++) {
         String leftSubstring = s.substring(0, i);
         String rightSubstring = s.substring(i, n);

         if (isPalindrome(leftSubstring, 0, i - 1)) {
            minSize = Math.min(minSize, n - i);
         }
         if (isPalindrome(rightSubstring, 0, n - i - 1)) {
            minSize = Math.min(minSize, i);
         }
      }

      return minSize;
   }

   public static void main(String[] args) {
      String s = "abccbaab";
      int result = minSizeSubstringToRemove(s);
      System.out.println("Minimum size substring to be removed: " + result);
   }
}

输出

Minimum size substring to be removed: 2
Open Compiler
# Function to check if a string is a palindrome
def is_palindrome(s, left, right):
   while left < right:
      if s[left] != s[right]:
         return False
      left += 1
      right -= 1
   return True
# Function to find the minimum size substring to be removed
def min_size_substring_to_remove(s):
   n = len(s)
   min_size = n

   for i in range(n + 1):
      left_substring = s[:i]
      right_substring = s[i:]

      if is_palindrome(left_substring, 0, i - 1):
         min_size = min(min_size, n - i)
      if is_palindrome(right_substring, 0, n - i - 1):
         min_size = min(min_size, i)

   return min_size

s = "abccbaab"
result = min_size_substring_to_remove(s)
print("Minimum size substring to be removed:", result)

输出

Minimum size substring to be removed: 2

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

测试用例示例

考虑以下字符串：“abccbaab”。可能的子串及其各自的回文状态如下：

  • 左子串 = ""，右子串 = "abccbaab"，回文 = false

  • 左子串 = "a"，右子串 = "bccbaab"，回文 = false

  • 左子串 = "ab"，右子串 = "ccbaab"，回文 = false

  • 左子串 = "abc"，右子串 = "cbaab"，回文 = false

  • 左子串 = "abcc"，右子串 = "baab"，回文 = false

  • 左子串 = "abccb"，右子串 = "aab"，回文 = true (左子串)

  • 左子串 = "abccba"，右子串 = "ab"，回文 = true (左子串)

  • 左子串 = "abccbaa"，右子串 = "b"，回文 = false

  • 左子串 = "abccbaab"，右子串 = ""，回文 = false

从上面的迭代中，我们可以看出，要移除的最小长度子串是2，当左子串是“abccba”而右子串是“ab”时发生这种情况。在这种情况下，移除右子串“ab”将使剩余的字符串“abccba”成为回文。

结论

在本文中，我们探讨了查找必须从给定字符串中移除的最小长度子串以使其成为回文的问题。我们提供了一个清晰有效的C++实现，它利用简单的循环来迭代字符串，创建子串并检查其回文状态，以找到必须移除的子串的最小长度。

通过理解此算法，您可以应用类似的概念来解决计算机科学和编程中的其他字符串操作和回文问题。

更新于：2023年10月27日

562 次浏览

开启你的职业生涯

完成课程后获得认证

开始学习
广告