將字串連線成 K 長度迴文串所需替換的最小字元數

找出需要更改的最少字元數以將給定字串轉換為 K 長度迴文子串的連線，是字串處理領域中的一個常見問題。迴文串是指正讀反讀都相同的字串，例如“radar”或“level”。本文將涵蓋解決此問題可使用的基本概念、方法和可能的最佳化策略。閱讀完畢後，讀者將能夠處理類似的字串操作問題，因為他們將全面瞭解所需的步驟。

接下來的段落將對問題進行完整的解釋，然後討論每種方法的優缺點。我們將對所選方法進行徹底檢查，並提供程式碼示例以演示如何使用它們。我們還將檢查每種方法的時間複雜度，以更深入地瞭解其在不同輸入大小下的效率。

使用的方法

  • 暴力法

  • 滑動視窗法

暴力法

查詢需要替換的最少字元數以形成 K 長度迴文串的字串連線的暴力法，包括檢查給定字串中長度為 K 的所有可能的子串。步驟如下：設定兩個指標，左指標和右指標，分別指向 K 字元子串的開頭和結尾；初始化一個變數來跟蹤最少的替換次數；迭代字串，每次右指標向右移動一步來更新視窗。對於每個視窗，透過比較左右字元來檢查它是否可以是迴文，如果不是迴文，則計算所需的替換次數。跟蹤迄今為止找到的最少替換次數。繼續此過程直到字串的結尾。結果將是實現指定的 K 長度迴文子串所需的最小替換次數。但是，這種方法具有較高的時間複雜度，對於大型字串來說效率低下。

演算法

  • 在遍歷給定字串時，考慮每個長度為 K 的子串。

  • 驗證每個子串是否是迴文。

  • 如果不是迴文，則計算需要更改多少個字元。

  • 保持替換次數最少的子串。

  • 透過更改最小替換子串中的字元來建立迴文。

示例

#include <iostream>
#include <string>
using namespace std;

string minimalReplacementPalindromeSubstring(const string& str, int K) {
   int n = str.length();
   string minReplacementSubstr;

   for (int i = 0; i <= n - K; i++) {
      string substr = str.substr(i, K);
      int replacements = 0;
      for (int j = 0; j < K / 2; j++) {
         if (substr[j] != substr[K - 1 - j]) {
            replacements++;
         }
      }

      if (replacements < minReplacementSubstr.length() || minReplacementSubstr.empty()) {
         minReplacementSubstr = substr;
      }
   }

   return minReplacementSubstr;
}

int main() {
   string input = "iurefhuhfrati";
   int K = 4;

   string result = minimalReplacementPalindromeSubstring(input, K);
   cout << "Minimal Replacement Substring: " << result << endl;

   return 0;
}

輸出

Minimal Replacement Substring: rati

滑動視窗法

滑動視窗法是一種用於有效解決問題的技術，包括子陣列或子串操作。在查詢需要替換的最少字元數以建立 K 長度迴文串的字串連線的上下文中，這種方法包括在遍歷輸入字串時保持 K 個字元的固定大小視窗（子串）。

演算法首先設定兩個指標 'left' 和 'right'，最初指向 K 字元子串的開頭和結尾。然後，它確定將此子串轉換為迴文所需的替換次數。初始化一個變數 'min_replacements' 來跟蹤所需的最小替換次數。

演算法

  • 設定兩個指標，left 和 right，指向第一個 K 字元子串的開頭和結尾。

  • 確定將子串轉換為迴文所需的替換次數。

  • 初始化變數 min_replacements 來跟蹤所需的最小替換次數。

  • 透過將右指標向右移動一個位置來更新視窗。

  • 如果當前視窗是迴文，則移動右指標。

  • 計算所需的替換次數，如果當前視窗不是迴文，則根據需要更改 min_replacements。

  • 透過將左指標向右移動一個位置來更新視窗。

  • 重複步驟 4 到 7，直到字串的結尾。

  • 用最少的替換次數替換子串的字元。

示例

#include <iostream>
#include <string>
using namespace std;

int minReplacementsForPalindrome(string s, int k) {
   int left = 0, right = k - 1, min_replacements = 0;
   while (right < s.length()) {
      int i = left, j = right;
      while (i < j) {
         if (s[i] != s[j])
            min_replacements++;
         i++;
         j--;
      }
      left++;
      right++;
   }
   return min_replacements;
}

int main() {
   string input_string = "abcxyzuvw"; // Replace this with your desired input string
   int k = 3; // Replace this with the desired value of K
   int result = minReplacementsForPalindrome(input_string, k);
   cout << "Minimum replacements required: " << result << endl;
   return 0;
}

輸出

Minimum replacements required: 7

結論

本文研究了查詢將給定字串轉換為 K 長度迴文子串的連線所需的最少字元數的問題。它探討了兩種解決此問題的方法：暴力法和滑動視窗法。暴力法包括檢查給定字串中長度為 K 的所有可能的子串，確定它們是否是迴文，並計算所需的替換次數。但是，這種方法具有很高的複雜度，對於大型字串來說效率低下。

另一方面，滑動視窗法透過保持固定大小的視窗並在遍歷輸入字串時有效地更新它來最佳化該方法。本文提供了程式碼示例和對每種方法的優缺點的見解，以幫助使用者理解並更有效地解決類似的字串操作問題。

更新於：2023年8月4日

瀏覽量：111

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告