C++ 通过指定的替换字符替换给定字符的所有出现

在这个问题中，我们需要根据字符对数组中给定的字符替换给定字符串的字符。我们将讨论解决这个问题的两种不同方法。在第一种方法中，我们遍历给定字符串的字符和字符对来替换每个字符。

在第二种方法中，我们将使用长度为26的数组来存储与每个字符相关的替换字符，并更改给定字符串的字符。

问题陈述 - 我们已经给出了一个包含N个小写字母字符的字符串str。同时，我们还给出了包含字符对的数组。我们需要将给定字符串的pairs[i][0]字符替换为pairs[i][1]。

示例

Input –  str = "xyz", pairs = {{'x', 'a'}, {'y', 'b'},, {'z', 'c'}}

Output – ‘abc’

说明

在这里，’x’被替换为’a’，’y’被替换为’b’，’z’被替换为’c’。

Input – str = "abderb", pairs = {{'a', 'e'}, {'b', 't'}, {'e', 'f'}, {'r', 's'}}

Output – ‘etdfst’

解释

在此字符串中，将 ‘a’ 替换为 ‘e’，将 ‘b’ 替换为 ‘t’，将 ‘e’ 替换为 ‘f’，将 ‘r’ 替换为 ‘s’。

方法1

在这种方法中，我们将遍历每一对字符，并在给定的字符串中替换匹配的字符。我们需要两个嵌套循环来迭代字符串的每一个字符。

步骤

• 步骤 1 - 将字符串的长度存储在 ‘N’ 变量中，并将数组的大小存储在 ‘M’ 变量中。

• 步骤 2 - 将字符串的副本存储在 ‘temp’ 变量中。

• 步骤 3 - 使用 for 循环遍历配对列表。

• 步骤 4 - 在循环中，将第一个字符存储在 ‘a’ 变量中，将第二个字符存储在 ‘b’ 变量中。

• 步骤 5 - 使用嵌套循环遍历字符串。

• 步骤 6 - 在嵌套循环中，如果给定字符串的当前字符等于 ‘a’，则将 temp 字符串中的当前字符替换为 ‘b’。

• 步骤 7 - 返回 temp 的值。

示例

#include <bits/stdc++.h>
using namespace std;
string replaceChars(string str, vector<vector<char>> pairs){
   // stror the size of the string and the array
   int N = str.size(), M = pairs.size();

   // Create a copy of the string str
   string temp = str;

   // Iterate over the array
   for (int x = 0; x < M; x++){

      // store the characters from the pair
      char a = pairs[x][0], b = pairs[x][1];

      // iterate over the string
      for (int y = 0; y < N; y++){

         // If the character is equal to a, then replace it with b
         if (str[y] == a){
            temp[y] = b;
         }
      }
   }
   return temp;
}
int main(){
   string str = "abderb";
   vector<vector<char>> pairs{{'a', 'e'},
      {'b', 't'},
      {'e', 'f'},
      {'r', 's'}};
   cout << "The string after replacing with the given characters is - " << replaceChars(str, pairs);
   return 0;
}

输出

The string after replacing with the given characters is - etdfst

时间复杂度 – O(N*M)，其中N是字符串的长度，M是字符对数组的长度。

空间复杂度 – O(N)，因为我们将新字符串存储在临时变量中。

方法2

在这种方法中，我们可以创建一个大小为26的数组。然后，我们可以将可替换的字符存储在当前字符的位置上。最后，我们可以从数组中获取可替换元素，并更新字符串的每个字符。

步骤

• 步骤1 - 获取字符串的大小’N’和数组的大小’M’。

• 步骤2 - 定义长度为26的’initial’和’final’数组。

• 步骤3 - 遍历字符串，并将’str[Y]’存储在’initial’和’final’数组的索引’str[Y] – a’的位置上。这里，str[Y] – ‘a’根据字符的ASCII值给出0到25之间的索引。

存储’str[Y]’在’initial’数组和’final’数组的’str[Y] – a’位置的原因是，如果字符串中存在任何字符，但在字符对中不存在，我们可以在最终字符串中保持它不变。

• 步骤4 - 遍历给定的字符对数组。在循环中，使用嵌套循环遍历’initial’数组。如果当前字符对的第一个字符与’initial’数组的字符相等，则使用当前字符对的第二个字符对更新’final’数组的字符。

• 步骤5 - 定义’result’变量，并初始化为空字符串。

• 步骤6 - 遍历输入字符串，从’final’数组中获取当前字符的对应字符，并将其附加到’result’字符串中。

• 步骤7 - 返回’result’字符串。

示例

#include <bits/stdc++.h>
using namespace std;
//  Function to replace the characters in the string
string replaceChars(string str, vector<vector<char>> pairs){

   // getting the size of the string and the vector
   int N = str.size(), M = pairs.size();

   // Declare two arrays of size 26
   char initial[26];
   char final[26];

   // Check all existing characters in the string
   for (int Y = 0; Y < N; Y++){
      initial[str[Y] - 'a'] = str[Y]; final[str[Y] - 'a'] = str[Y];
   }

   // Iterate over the range [0, M]
   for (int X = 0; X < M; X++){

      // get characters from the vector
      char a = pairs[X][0], b = pairs[X][1];

      // Iterate over the range [0, 26]
      for (int Y = 0; Y < 26; Y++){

         // If the character is the same as a, then replace it with b in the final array
         if (initial[Y] == a){
            final[Y] = b;
         }
      }
   }
   string result = "";

   // get the final string using the final array
   for (int Y = 0; Y < N; Y++){
      result += final[str[Y] - 'a'];
   }
   return result;
}
int main(){
   string str = "aberb";
   vector<vector<char>> pairs{{'a', 'e'},
      {'b', 't'},
      {'e', 'f'},
      {'r', 's'}};
   cout << "The string after replacing with the given characters is - " << replaceChars(str, pairs);
   return 0;
}

输出

The string after replacing with the given characters is - etfst

时间复杂度 – O(N)，因为它是一个嵌套循环，仅进行恒定次数的迭代。

空间复杂度 – O(1)，因为它使用一个长度为26的数组，这是一个常数。