使所有给定的字符串相等的字符重新排列的次数最小化

这里的目标是确定在给定大小为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中文网其他相关文章！