修改字串陣列，替換在同一字串或剩餘字串中重複出現的字元

修改字串陣列，替換在同一字串或剩餘字串中重複出現的字元，是程式設計中一個常見的問題。它可以使用雜湊表、集合、陣列等方法解決。目標是在提供相同功能的同時，改進時間和空間需求。這個問題在許多現實場景中都會遇到，例如處理大型文字或清理包含重複項的資料集。

問題陳述

給定一個包含小寫和大寫字元的輸入字串陣列 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 次瀏覽

開啟您的 職業生涯

透過完成課程獲得認證

開始學習
廣告