修改字符串数组，替换在同一字符串或剩余字符串中重复出现的字符

修改字符串数组，替换在同一字符串或剩余字符串中重复出现的字符，是编程中一个常见的问题。它可以使用哈希表、集合、数组等方法解决。目标是在提供相同功能的同时，改进时间和空间需求。这个问题在许多现实场景中都会遇到，例如处理大型文本或清理包含重复项的数据集。

问题陈述

给定一个包含小写和大写字符的输入字符串数组 arr[]。目标是通过删除字符串中在同一字符串或数组中其他字符串中重复出现的字符来修改数组。

示例 1

输入

arr[] = {“apple”, “Banana”, “coding”}

输出

arr[] = {“aple”, “Bn”, “codig”}

解释

对于 arr[0] = “apple”，字符 ‘p’ 是字符串中唯一重复的字符，因此修改后的 arr[0] = “aple”

对于 arr[1] = “Banana”，字符 ‘a’ 重复，‘n’ 也重复，因此修改后的 arr[1] = “Bn”

对于 arr[2] = “coding”，字符 ‘n’ 重复，因此修改后的 arr[2] = “codig”

示例 2

输入

arr[] = {“Stay”, “This”, “Hill”}

输出

arr[] = {“Stay”, “This”, “Hl”}

解释

对于 arr[0] = “Stay”，没有重复字符，因此修改后的 arr[0] = “Stay”

对于 arr[1] = “This”，没有重复字符，因此修改后的 arr[1] = “This”

对于 arr[2] = “Hill”，字符 ‘i’ 和 ‘l’ 重复，因此修改后的 arr[2] = “Hl”

方法：使用集合

为了删除给定字符串数组中重复的字符，可以使用集合。可以使用无序集合来记录我们在迭代数组字符串时遇到的不同字符。迭代数组中的每个字符串，然后迭代字符串中的每个字符，检查集合中是否存在每个字符，如果存在，则将该字符添加到集合中并附加修改后的字符串，否则跳过它。

算法

以下是给定 C++ 程序的算法：

  • 定义一个函数 removeDuplicates，它接受一个字符串向量 arr 作为输入。

  • 声明一个字符的无序集合 uniqueChar 来存储不同的字符。

  • 确定数组的大小 n。

  • 声明一个空的字符串向量 ans 来存储修改后的字符串列表。

  • 使用 for 循环遍历数组，并迭代 arr 中的每个字符串 str。

  • 声明一个空字符串 temp 来存储修改后的字符串。

  • 使用 for 循环遍历 str 中的每个字符 ch。

  • 如果 ch 已经在 uniqueChar 中，则继续下一个字符。

  • 否则，将 ch 附加到 temp 并将 ch 插入到 uniqueChar 中。

  • 如果 temp 不是空字符串，则将其推入向量 ans 中。

  • 使用 for 循环遍历 ans 向量并打印每个字符串。

  • 在 main 函数中，使用给定的输入字符串定义一个字符串数组 arr。

  • 调用 removeDuplicates 函数，并将 arr 作为输入传递。

示例：C++ 实现

在以下程序中，我们使用一个无序集合来跟踪字符串数组中所有唯一的字符。每个字符首先在集合中进行检查以查看先前的出现情况，然后决定是将其保留在修改后的字符串中还是不保留。

#include <bits/stdc++.h>
using namespace std;
// Function to remove duplicate characters across the strings
void removeDuplicates(vector<string> arr){

   // Unordered set stores the unique characters in the given array of strings
   unordered_set<char> uniqueChar;
   int n = arr.size();
   vector<string> ans;
   
   // traversing the array to get all the strings individually
   for (auto str : arr) {
      string temp = "";
      
      // Iterating over the characters of the string
      for (auto ch : str) {
      
         // If character has not occurred before and is not present in the set
         if (uniqueChar.find(ch) == uniqueChar.end()) {
         
            // Adding the character to the modified string and the set
            temp += ch;
            uniqueChar.insert(ch);
         }
         
         // If ch is present in the set then it had occurred before thus just skip it
      }

      ans.push_back(temp);
   }
   
   // Printing the list of modified strings
   for (int i = 0; i < ans.size(); i++) {
      cout << ans[i] << " ";
   }
}

int main(){
   vector<string> arr= { "Stay", "This", "Hill" };
   removeDuplicates(arr);
}

输出

Stay This Hl

时间复杂度 - O(nm)，其中 n 是输入数组的大小，m 是最大字符串的大小。

空间复杂度 - O(n)

结论

总之，我们可以通过一个简单的算法来修改字符串数组，替换跨越字符串的重复字符。我们可以使用一个集合来存储不同的字符。该算法效率很高，时间复杂度为 O(nm)，但可以通过以下方式进一步优化：

  • 通过引用而不是通过值传递向量，以避免复制整个向量。

  • 在迭代向量时使用常量引用，以避免复制每个元素。

更新于： 2023-07-25

154 次浏览

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告