无需额外空间的 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.