通过将给定字符的所有出现替换为指定的替换字符来修改字符串

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

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

问题陈述 − 我们给定了一个包含N个小写字母字符的字符串str。同时，我们给定了包含字符对的数组。我们需要用pairs[i][1]替换给定字符串中的pairs[i][0]字符。

示例例子

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 - 将字符串的大小存储在变量 'N' 中，并将数组存储在变量 'M' 中。

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

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

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

• 第5步 - 使用嵌套循环迭代字符串。

• 步骤 6 − 在嵌套循环中，如果给定字符串的当前字符等于 'a'，则将当前字符替换为 'b' 在临时字符串中。

• 第7步 - 返回temp的值。

示例

#include 
using namespace std;
string replaceChars(string str, vector> 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> 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)，因为我们将新字符串存储在temp变量中。

方法二

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

算法

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

• 第二步 - 定义长度为26的“初始”和“最终”数组。

• 第三步 - 遍历字符串并将str[Y]存储在“str[Y] - a”的初始和最终数组索引中。这里，str[Y] - 'a'根据字符的ASCII值给出0到25之间的索引。

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

• 第四步 - 迭代给定的字符对数组。在循环中，使用嵌套循环来迭代初始数组。如果当前字符对的第一个字符等于“initial”数组的字符，则使用当前字符对的第二个字符对更新“final”数组的字符。

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

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

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

示例

#include 
using namespace std;
//  Function to replace the characters in the string
string replaceChars(string str, vector> 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> 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的数组，是常数。