回文是一種正向和反向讀取都相同的字符序列。在計(jì)算機(jī)科學(xué)和編程中，回文是字符串操作問題中常見的主題。在本文中，我們將探討如何找到必須從給定字符串中刪除的最小大小的子串，使其成為回文。我們將提供一個(gè)結(jié)構(gòu)良好的C++解決方案，并包含一個(gè)示例來說明測(cè)試用例。

問題陳述

給定長度為'n'的字符串's'，我們需要找到應(yīng)該刪除的子字符串的最小大小，以使剩下的字符串成為回文。

算法

• 創(chuàng)建一個(gè)名為isPalindrome的函數(shù)，它以字符串's'作為參數(shù)，并在其為回文時(shí)返回true，否則返回false。

• 創(chuàng)建一個(gè)名為minSizeSubstringToRemove的函數(shù)，它以字符串's'作為參數(shù)。

• 將變量'minSize'初始化為字符串的長度。

• 使用循環(huán)迭代字符串，從0到'n'遞增一個(gè)索引'i'。

• 在每次迭代中，執(zhí)行以下步驟 ?

• 從字符串的開頭到索引'i'創(chuàng)建兩個(gè)子字符串，另一個(gè)從索引'i'到字符串的末尾。

• 檢查其中任意一個(gè)子字符串是否為回文。

• 如果任一子字符串是回文，將'minSize'更新為非回文子字符串的長度和'minSize'之間的最小值。

• 將'minSize'作為結(jié)果返回。

示例

#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

測(cè)試用例示例

考慮以下字符串："abccbaab"。可能的子字符串及其對(duì)應(yīng)的回文狀態(tài)如下：

• 左子字符串 = ""，右子字符串 = "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

從上面的迭代中，我們可以看到，要?jiǎng)h除的最小大小的子字符串是2，當(dāng)左子字符串是"abccba"，右子字符串是"ab"時(shí)發(fā)生。在這種情況下，刪除右子字符串"ab"將使剩余的字符串"abccba"成為回文。

結(jié)論

在本文中，我們探討了尋找最小大小子串的問題，該子串必須被刪除以使給定字符串成為回文。我們提供了一個(gè)清晰高效的C++實(shí)現(xiàn)，利用一個(gè)簡單的循環(huán)來遍歷字符串，創(chuàng)建子串并檢查它們的回文狀態(tài)，以找到必須被刪除的子串的最小大小。

通過理解這個(gè)算法，你可以將類似的概念應(yīng)用于解決計(jì)算機(jī)科學(xué)和編程中的其他字符串操作和回文問題。

以上是最小的子串需要被刪除才能使給定的字符串成為回文的詳細(xì)內(nèi)容。更多信息請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！