無需額外空間的 C++ 程式，用於替換字串中所有出現的“AB”為“C”

在本文中，我們將用“C”替換給定字串（包含大寫拉丁字元）中所有出現的“AB”。所有“AB”都將變成“C”，但單個“A”和“B”不會受到影響。

讓我們來看一些輸入場景：

讓我們假設一個字串“ABOUTME”

Input: "ABOUTME"
Result: COUTME

我們從索引 1 開始遍歷字串。然後我們分別檢查當前元素和前一個元素是否為“B”和“A”。如果找到，我們將最後一個附加的字元（“A”）替換為“C”。

當輸入字串中不存在子字串“AB”時，將出現最壞情況下的時間複雜度。例如，考慮字串“cloud”

Input: "CLOUD"
Result: CLOUD

整個字串都被遍歷，但沒有找到“AB”子字串。

讓我們也來看一下輸入字串中包含字元“A”和“B”，但它們並不連續的情況。

Input: "ALIBI"
Result: ALIBI

輸出字串保持不變，因為子字串 AB 沒有連續地出現在輸入字串中。

演算法

  • 任何字串作為輸入並被遍歷。

  • 字串中的每個元素都與子字串“AB”的字元（即“A”和“B”）進行比較。

  • 如果找到匹配項，則字串的大小減少 1，並將“AB”替換為“C”。

  • 得到的字串作為包含替換字母的輸出。

示例

例如，讓我們取一個字串 = “TUTORIALSABPOINT”，我們將實現一個 C++ 程式來檢查字串中是否存在“AB”，並將其替換為字元“C”：

#include <iostream>
using namespace std;
string solve(string s) {
   if(s.size() == 0) return s;
   string ans = "";
   ans+=s[0];
   for(int i=1;i<s.size();i++) {
      if(s[i] == 'B' && s[i-1] == 'A') {
         ans[ans.size()-1] = 'C';
      }
      else {
         ans+=s[i];
      }
   }
   return ans;
}
int main() {
   string s = "TUTORIALSABPOINT";
   cout << solve(s) << endl;
   return 0;
}

輸出

TUTORIALSCPOINT

示例

解決這個問題的另一種方法是使用兩個索引。我們將使用一個索引來跟蹤原始字串，另一個索引用於跟蹤修改後的字串。當我們在索引 j（例如原始字串）處遇到“AB”時，我們將 j 加 2，並將 i（例如修改後的字串）加 1。如果不是，我們將透過複製字元來分別遞增每個索引。

#include <iostream>
using namespace std;
string solve(string s) {
   int i = 0;
   int j = 0;
   int terminatingIndex = s.size();
   while (j<s.size()-1) {
      if (s[j] == 'A' && s[j+1] == 'B') {
         j = j + 2;
         s[i++] = 'C';
         continue;
      }
      s[i++] = s[j++];
   }
   if (j==s.size()-1) {
      s[i++] = s[j];
   }
   terminatingIndex = i;
   return s.substr(0, terminatingIndex);
}
int main() {
   string s= "ARTICLESABPOINT";
   cout << solve(s);
   return 0;
}

輸出

ARTICLESCPOINT

結論

只需從索引 1 遍歷字串即可計算我們的新字串並檢查字串中是否存在“AB”。我們建立了一個 ans 字串來獲取唯一的字串，但除了這個之外，我們沒有使用任何額外的空間。

更新於：2022年8月10日

429 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告
© . All rights reserved.