最小的子字串需要被刪除才能使給定的字串成為回文

回文是一種正向和反向讀取都相同的字元序列。在電腦科學和程式設計中，回文是字串操作問題中常見的主題。在本文中，我們將探討如何找到必須從給定字串中刪除的最小大小的子字串，使其成為回文。我們將提供一個結構良好的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

• 左子字串 = "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 實現，利用一個簡單的循環來遍歷字串，建立子字串並檢查它們的回文狀態，以找到必須被刪除的子字串的最小大小。

透過理解這個演算法，你可以將類似的概念應用於解決電腦科學和程式設計中的其他字串操作和回文問題。

以上是最小的子字串需要被刪除才能使給定的字串成為回文的詳細內容。更多資訊請關注PHP中文網其他相關文章！