使所有給定的字串相等的字元重新排列的次數最小化

這裡的目標是確定在給定大小為n的字串陣列Str的任意運算元下，是否可以使所有字串相同。任何元素都可以從字串中取出並在同一個或另一個字串中的任意位置放回，所有操作可以在一次動作中完成。如果可以使字串相等，則傳回"Yes"，否則傳回"No"，並給予所需的最少操作次數。

問題陳述

實作一個程序，以最小化重新排列字元的次數，使所有給定的字串相等

範例範例1

Let us take the Input: n = 3, 
The input array, Str = {mmm, nnn, ooo}

The output obtained : Yes 6

解釋

數組Str中提供的三個字串可以透過最少6次操作變成相同的字串mno。

{mmm, nnn, ooo} −> {mm, mnnn, ooo}
{mm, mnnn, ooo} −> {m, mnnn, mooo}
{m, mnnn, mooo} −> {mn, mnn, mooo}
{mn, mnn, mooo} −> {mn, mn, mnooo}
{mn, mn, mnooo} −> {mno, mn, mnoo}
{mno, mn, mnooo} −> {mno, mno, mno}

範例範例2

Let us take the Input: n = 3, 
The input array, Str = {abc, aab, bbd}

The output obtained: No

解釋

使用提供的字串陣列Str，不能產生相同的字串。

範例範例3

Let us take the Input: n = 3, 
The input array, Str = {xxy, zzz, xyy}

The output obtained : Yes 4

解釋

所有提供的陣列Str的三個字串都可以透過最少4次操作變成相同的字串xyz。

解決方案方法

為了最小化重新調整字元的次數，使所有給定的字串相等，我們使用以下方法。

解決這個問題的方法是最小化字元重新定位的次數，以使所有給定的字串相等

如果字母在所有字串中均勻分佈，那麼可以實現使所有字串相等的目標。也就是說，數組中每個字元的頻率需要被大小為 "n" 的數整除。

演算法

將所有給定字串相等所需的最小字元重新定位演算法如下所示

• 步驟 1 − 開始

• #第二步 - 定義一個函數來檢查字串是否可以變得相同

• #步驟 3 - 定義一個陣列來儲存所有字元的頻率。這裡我們定義了"fre"。

• 第四步 − 遍歷提供的字串陣列。

• 第5步 - 遍歷給定字串Str的每個字元。

• 步驟 6 - 更新取得到的頻率

• 第7步 - 現在檢查每個字母的字元

• 步驟 8 - 如果頻率無法被大小為 n 的數整除，則列印 "No"

• #第9步 - 將每個字元的頻率除以大小n

• #第10步 - 定義一個整數變數"result"並將得到的結果儲存為最小操作次數

• #步驟 11 - 儲存原始字串 "org" 中每個字元的頻率

• 第12步 - 同樣取得額外字元的數量

• 第13步 - 列印Yes和獲得的結果。

• 第14步 − 停止

#範例：C程式

這是上述演算法的C程式實現，用於最小化重新定位字元的次數，以使所有給定的字串相等。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
// Define a function to check if the strings could be made identical or not
void equalOrNot(char* Str[], int n){

   // Array fre to store the frequencies of all the characters
   int fre[26] = {0};
   
   // Traverse the provided array of strings
   for (int i = 0; i < n; i++) {
   
      // Traverse each characters of the given string Str
      for (int j = 0; j < strlen(Str[i]); j++){
         // Update the frequencies obtained
         fre[Str[i][j] - 'a']++;
      }
   }
   
   // now check for every character of the alphabet
   for (int i = 0; i < 26; i++){
   
      // If the frequency is not divisible by the size n, then print No.
      if (fre[i] % n != 0){
         printf("No\n");
         return;
      }
   }
   
   // Dividing the frequency of each of the character with the size n
   for (int i = 0; i < 26; i++)
      fre[i] /= n;
      
   // Store the result obtained as the minimum number of operations
   int result = 0;
   for (int i = 0; i < n; i++) {
   
      // Store the frequency of each od the characters in the original string org
      int org[26] = {0};
      for (int j = 0; j < strlen(Str[i]); j++)
         org[Str[i][j] - 'a']++;
         
      // Get the number of additional characters as well
      for (int i = 0; i < 26; i++){
         if (fre[i] > 0 && org[i] > 0){
            result += abs(fre[i] - org[i]);
         }
      }
   }
   printf("Yes %d\n", result);
   return;
}
int main(){
   int n = 3;
   char* Str[] = { "mmm", "nnn", "ooo" };
   equalOrNot(Str, n);
   return 0;
}

輸出

Yes 6

結論

同樣地，我們可以最小化字元重新定位的次數，以使所有給定的字串相等。

在本文中，解決了獲取程序以最小化字元重新定位次數以使所有給定字串相等的挑戰。

提供了C程式碼以及演算法，以最小化重新排列字元的次數，使得所有給定的字串相等。

以上是使所有給定的字串相等的字元重新排列的次數最小化的詳細內容。更多資訊請關注PHP中文網其他相關文章！